传送门
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了 小X。小X很开心地收下了。 然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
包含多组测试数据。文件第一行有一个整数 T，表示测试 数据的组数。 第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。
含T 行，分别对每组数据作出回答。第 i 行输出相应的 第Ki 个不是完全平方数的正整数倍的数。
1 13 100 1234567
对于 100%的数据有 1 ≤ Ki ≤ 10^9 , T ≤ 50
HOME Back
解题思路：
这是算做的莫比乌斯反演的第一题了，应该叫启蒙题。。。感觉题目描述的有点问题，因为 1 也是
完全平方数呀，但是 题目描述中没有将 1 排除，如果有 1 的话 也就没有任何数可以输出了，其实
不含平方数的倍数，其实换一个意思就是说：将一个数质因子分解之后，素因子的指数都是 1 ，那
么我们可以这么想如果我们知道一个范围的话 [1,x] ，那么我们就可以转为在 [1,x] 区间中找第 k
个数，那么就用到了二分查找，那么我们大约确定一下 x 的范围是多少，好像大约是 2∗k 左右，
这个好像是通过什么乱七八糟的公式推出来的，这个题目的重点不是它，而是莫比乌斯，首先我们
可以发现， [1,x] 区间中找不含完全平方数的个数的时候，应该通过容斥原理来做：
ans=0个质数乘积的平方的倍数−1个质数乘积的平方的倍数的(22的倍数32的倍数的...)+2个
质数乘积的平方的倍数...
因为数据太大了，如果通过二进制枚举来做的话显然是不可行的，所以我们需要找到合适的方法，
然后我们通过观察容斥原理的符号正好跟莫比乌斯函数 mu(x) 的符号一样，这是巧合吗。。。感
叹出题人的强大，那么我们就通过线性筛得到 mu(x) 函数，然后容斥原理一下，得到结果，最后
在通过二分答案就可以了。
My Code：
/** 2016 - 08 - 15 上午 Author: ITAK Motto: 今日的我要超越昨日的我，明日的我要胜过今日的我， 以创作出更好的代码为目标，不断地超越自己。 **/ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <set> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9+5; const int MAXN = 1e5+5; const int MOD = 1e9+7; const double eps = 1e-7; const double PI = acos(-1); using namespace std; LL Scan()///输入外挂 { LL res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } void Out(LL a)///输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int mu[MAXN], p[MAXN], k; bool prime[MAXN]; void Init() { memset(prime, 0, sizeof(prime)); k = 0; for(int i=2; i<MAXN; i++) { if(!prime[i]) { p[k++] = i; mu[i] = -1; } for(int j=0; j<k&&i*p[j]<MAXN; j++) { prime[i*p[j]] = 1; if(i%p[j] == 0) { mu[i*p[j]] = 0; break; } mu[i*p[j]] = -mu[i]; } } } LL Judge(LL x) { LL tmp = (LL)sqrt(x+0.5), ans = x; for(LL i=2; i<=tmp; i++) ans += mu[i] * (x/(i*i)); return ans; } int main() { Init(); LL T, k; T = Scan(); while(T--) { k = Scan(); LL l = 1, r = (k<<1), mid; while(l <= r) { mid = ((l+r)>>1); if(Judge(mid)>=k) r = mid-1; else l = mid+1; } printf("%lld\n",r+1); } return 0; }