当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [P4318] 完全平方数

[P4318] 完全平方数

2018年12月28日  | 移动技术网IT编程  | 我要评论

ca4305,思可觅,昨夜谁为

想不出什么办法能直接算的（别跟我提分块打表），不如二分答案吧：设\(f(x)=\sum_{i=1}^n [i不是“完全平方数”]\), 显然f(x)与x正相关。再结合筛法、容斥，不难得到：
\[ f(x)=\sum_{i=1}^{sqrt x } \mu(i)\lfloor\frac{x}{i^2}\rfloor \]
找到那个满足f(x)==k的x就行了。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int n=1e6+10;

int mu[n],pr[n],cnt;
bool vis[n];

void predure() {
    mu[1]=1;
    for(int i=2; i<n; ++i) {
        if(!vis[i]) mu[pr[++cnt]=i]=-1;
        for(int j=1; j<=cnt && i*pr[j]<n; ++j) {
            vis[i*pr[j]]=1;
            if(i%pr[j]==0) break;
            mu[i*pr[j]]=-mu[i];
        }
    }
}
int f(int x) {
    int ret=0;
    for(int i=1; i<=x/i; ++i) {
        ret+=mu[i]*(x/(i*i));
    }
    return ret;
}

signed main() {
    predure();
    int t,k;
    scanf("%lld",&t);
    while(t--) {
        scanf("%lld",&k);
        int l=1,r=k*2,mid,ans;
        while(l<=r) {
            mid=(l+r)>>1;
            if(f(mid)>=k) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网