做网站南宁,个人网站也要备案吗,wordpress 插件扫描,万维网域名注册网站Time Limit: 10 Sec Memory Limit: 128 MB Submit: 5160 Solved: 2515 [Submit][Status][Discuss] Description 小 X 自幼就很喜欢数。但奇怪的是#xff0c;他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此#xff0c;他也讨厌所有是完全平方数的正整数倍的… Time Limit: 10 Sec Memory Limit: 128 MB Submit: 5160 Solved: 2515 [Submit][Status][Discuss] Description 小 X 自幼就很喜欢数。但奇怪的是他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。 这天是小X的生日小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌的数。他列出了所有小X不讨厌的数然后选取了第 K个数送给了 小X。小X很开心地收下了。 然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗 Input 包含多组测试数据。文件第一行有一个整数 T表示测试 数据的组数。 第2 至第T1 行每行有一个整数Ki描述一组数据含义如题目中所描述。 Output 含T 行分别对每组数据作出回答。第 i 行输出相应的 第Ki 个不是完全平方数的正整数倍的数。 Sample Input 4 1 13 100 1234567 Sample Output 1 19 163 2030745 HINT 对于 100%的数据有 1 ≤ Ki ≤ 10^9 , T ≤ 50 题解 一看到完全平方数的倍数自然而然就想到莫比乌斯函数又因为数据范围较大
就想到二分来解决所以先筛出莫比乌斯函数之后根据容斥原理算出不是完全
平方数的倍数的个数。有些地方还是理解的不够透彻。代码 #includebits/stdc.h
#define LL long longusing namespace std;
const int MAXN 1e55;int n,miu[MAXN],cnt,prime[MAXN],T;
bool vis[MAXN];inline LL check(LL x){int xx(int)sqrt(x);LL ret0;for(register int i1;ixx;i)retmiu[i]*(x/(i*i));return ret;
}signed main(){miu[1]1;for(register int i2;iMAXN;i){if(!vis[i]) {vis[i]1;prime[cnt]i;miu[i]-1;}for(register int j1;jcnt (LL)prime[j]*iMAXN;j){vis[(LL)i*prime[j]]1;if(i%prime[j]0){miu[(LL)i*prime[j]]0;break;}else miu[(LL)i*prime[j]]-miu[i];}}scanf(%d,T);while(T--){scanf(%d,n);LL l0,rn*2;while(lr){LL mid(lr)1;if(check(mid)n) lmid1;else rmid;}printf(%lld\n,r);}return 0;
} 转载于:https://www.cnblogs.com/sdfzsyq/p/9677025.html
