bzoj 2986 Non-Squarefree Numbers
Description
一个正整数K被称为squarefree,如果它没有一个D^2(D>1)这样的约数。
Input
读入一个正整数N
Output
找出第N个不是squarefree的数。1<=N<=10^10
Sample Input
10
Sample Output
27
Hint
前10个非squarefree的数
4 8 9 12 16 18 20 24 25 27
题解
和上面一样。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <cstdio> #include <algorithm> #define mid (l + r >> 1) using namespace std; const int N = 1000000; bool flag[N + 10]; int T, mu[N + 10], pr[N + 10]; long long k; void init() { mu[1] = 1; for (int i = 2; i <= N; ++i) { if (!flag[i]) pr[++pr[0]] = i, mu[i] = -1; for (int j = 1; j <= pr[0] && i * pr[j] <= N; ++j) { flag[i * pr[j]] = 1; if (i % pr[j] == 0) { mu[i * pr[j]] = 0; break; } mu[i * pr[j]] = -mu[i]; } } } long long check(long long x) { long long ans = 0; for (long long i = 2; i * i <= x; ++i) ans -= mu[(int)i] * (x / (i * i)); return ans; } main() { init(); scanf("%lld", &k); long long l = 1, r = 30000000000ll; while (l <= r) if (check(mid) >= k) r = mid - 1; else l = mid + 1; printf("%lld\n", l); } |