首先显然二分答案。 如果二分到的数为 \(n\)，考虑设 \(f(x)\) 表示 \(n\) 以内最大平方因子为 \(x^2\) 的数的个数。
设 \(F(x) = \sum\limits_{x|d} f(d) = \lfloor\frac n{x^2}\rfloor\)。
有 \(f(x) = \sum\limits_{x|d} \mu(\frac d x) f(d)\)。
以上为莫反公式。
然后求出 \(f(1) = \sum\limits_{i=1}^{\lfloor\sqrt n\rfloor} \mu(i) \lfloor \frac n{i^2}\rfloor\) 就是我们用来判定答案的东西了。
代码： 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
using namespace std;
const int MX = 1e5;
int T,k;
int vis[MX + 5],cnt,prime[MX + 5],mu[MX + 5];
long long l,r,mid,ans;
int check()
{
long long ans = 0;
for(register int i = 1;(long long)i * i <= mid;++i)
ans += mu[i] * (mid / i / i);
return k <= ans;
}
int main()
{
mu[1] = 1;
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
scanf("%d",&T);
for(;T;--T)
{
scanf("%d",&k),l = 1,r = 1e10;
while(l <= r)
mid = l + r >> 1,check() ? (ans = mid,r = mid - 1) : (l = mid + 1);
printf("%lld\n",ans);
}
}