题解：P4318 完全平方数

· · 题解

题目传送门

1.题目大意：
别看题目说的那么长，其实主要意思就是的求第 K 个不是完全平方数和完全平方数的倍数的数。当然，1 不是完全平方数，参考样例。

2.题目思路：
主要思路：容斥原理+二分答案
我们为什么能够二分答案？
我们通过样例可以得出我们实际上就是要求出一个最小 ans ，使得 1 至 ans 中不是完全平方数和完全平方数的倍数的数的个数恰好大于或等于 K，因为这个求解的过程具有单调性，所以可以用二分求解。
所以现在问题就转移到了如何求出 1 至 ans 中有多少个不是完全平方数和完全平方数的倍数的数，即 1 至 ans 中有多少个是完全平方数和完全平方数的倍数的数。
容斥原理
我们可以发现在 1 至 n 中 4 的倍数有 [\frac{n}{4}] 个，所以我们就不会计算 1 至 n 中 8，12 ......等 4 的倍数，因为这样就会重复计算，这样就可以用到容斥原理了。所以最终的答案为 [\frac{n}{2 _ {} ^ {2}}] 加上 [\frac{n}{3 _ {} ^ {2}}] 加上 [\frac{n}{5 _ {} ^ {2}}] ......再减去 [\frac{n}{6 _ {} ^ {2}}] 减去 [\frac{n}{10 _ {} ^ {2}}] 再减去 [\frac{n}{15 _ {} ^ {2}}] ......
因为这样的时间复杂度较高，所以我们只需要判断 1 至 n 中每个数到底是加还是减还是不计算，判断方法就是分解质因数，判断它的质因数是否有重复和质因数个数是单数还是偶数，详细见代码。 

#include<bits/stdc++.h>
using namespace std;
long long t,k,phi[45010];
long long work(long long x){
    long long cnt=0;
    for(int i=2;i<=sqrt(x);i++){
        cnt+=phi[i]*(x/(i*i));
    }
    return cnt;
}
int main(){
    scanf("%lld",&t);
    for(int i=2;i<=45000;i++){//判断它是加还是减还是不计算
        long long cnt=0,s=0,a=i;
        for(int j=2;j<=sqrt(i);j++){
            long long js=0;
            while(a%j==0){
                a/=j;
                js++;
            }
            cnt+=js;
            if(js>1){
                s=1;
                break;
            }
        }
        if(a>1)cnt++;
        if(s==1)continue;
        if(cnt%2==0)phi[i]=-1;
        else phi[i]=1;
    }
    while(t--){//二分
        scanf("%lld",&k);
        long long l=1,r=2e9,ans;
        while(l<=r){
            long long mid=(l+r)/2;
            if(mid-work(mid)>=k){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}