bzoj 2986 Non-Squarefree Numbers

内容

Description

一个正整数K被称为squarefree,如果它没有一个D^2(D>1)这样的约数。

Input

读入一个正整数N

Output

找出第N个不是squarefree的数。1<=N<=10^10

Sample Input

Sample Output

Hint

前10个非squarefree的数

4 8 9 12 16 18 20 24 25 27

题解

和上面一样。。

#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);
}