牛牛做数论

牛牛做数论

#includeusing namespace std;const int N = 1e5 + 10;int primes[N], cnt;bool st[N];void get () { for (int i =2; i<= 1000; i ++) { if (!st[i]) primes[++cnt] = i; for (int j = 1;primes[j] * i <=1000; j ++) { st[primes[j] * i] = 1; if (i % primes[j] == 0) break; } }}bool check(int tar) { for (int i = 2; i<= tar / i; i ++) if (tar % i == 0) return 0; return 1;}void solve() { int n; cin >> n; if (n == 1) { puts("-1"); return; } long long ans = 1; for (int i =1; i<= cnt; i++) if (ans * primes[i] <= n) ans *= primes[i]; else { cout << ans << " "; break; } for (int i = n; i >= 2; i --) if (check(i)) { cout << i << " "; puts(""); break; } }int main () { int t; get(); cin >>t; while (t --) solve(); return 0;}

当看到这个题的时候，第一时间是在想暴力，暴力肯定超时，但是没有继续想有什么快速的做法。有结论就有快速的做法。而且也没有第一时间反应出来欧拉函数的公式.下次遇到公式需要反应出来他的公式，尝试推一下，把公式化简。 这题通过化简可以的得到

问题1：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。