题意:输出第k小的无平方因子的数
无平方因子数：分解质因子后，所有质因数的次数都为1
求第k小，考虑二分答案
我们发现，如果直接去找[1,x]的无平方因子数的个数，我们发现，可能对于多个x，[1,x]内的无平方因子数是一样的，所以我们不能找到确切的答案
既然不能直接求，考虑补集思想，我们只要找出[1,x]内有多少个有平方因子的数，再用x减去即可，并且我们可以找到确切的答案
根据不重不漏原则，我们考虑容斥原理：
[1,x]内有平方因子的数=x-有一个质因数的次数为2的数的倍数的数的数量+有两个质因数次数为2的数的倍数的数的数量-...（x可以看做1的倍数的个数）
然后根据莫比乌斯函数的定义，对于每个乘积a，前面的符号刚好是μ（a），而x内有floor（x/a*a) 个 a*a的倍数的数
所以[1,x]内，有 sigma（μ(i)*floor(x/a*a)) ( 1<=i<=sqrt(x) ) 个无平方因子的数
const inf= 1644934500; var t,l,mid,x,ans,r :longint; vis :array[0..41010] of boolean; pri,miu :array[0..41010] of longint; procedure pre_do; var i,j:longint; tt:longint; begin miu[1]:=1; for i:=2 to trunc(sqrt(inf)) do begin if not vis[i] then begin inc(t); pri[t]:=i; miu[i]:=-1; end; for j:=1 to t do if (i*pri[j]>trunc(sqrt(inf))) then break else begin vis[i*pri[j]]:=true; if (i mod pri[j]<>0) then miu[i*pri[j]]:=-miu[i] else begin miu[i*pri[j]]:=0; break; end; end; end; end; function solve(x:longint):longint; var ans:longint; i:longint; begin ans:=0; for i:=1 to trunc(sqrt(x)) do inc(ans,miu[i]*(x div (i*i))); exit(ans); end; begin pre_do; read(t); while (t>0) do begin dec(t); read(x); l:=1;r:=inf; while (l<=r) do begin mid:=(int64(l)+int64(r)) div 2; if solve(mid)>=x then begin ans:=mid;r:=mid-1; end else l:=mid+1; end; writeln(ans); end; end. ——by Eirlys
