BZOJ 2440 「中山市选 2011」完全平方数

首先显然二分答案。 如果二分到的数为 n，考虑设 f(x) 表示 n 以内最大平方因子为 x2 的数的个数。

设 F(x)=∑x|df(d)=⌊nx2⌋。
有 f(x)=∑x|dμ(dx)f(d)。
以上为莫反公式。
然后求出 f(1)=⌊√n⌋∑i=1μ(i)⌊ni2⌋ 就是我们用来判定答案的东西了。

代码：

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