传送门
题意简述：qqq次询问(q≤500)(q\le500)(q≤500)，每次问第kkk个不被除111以外的完全平方数整除的数是多少(k≤1e9)(k\le1e9)(k≤1e9)。
思路：考虑二分答案为xxx，然后用容斥原理来解决，ans=n−只有一个质数因子次数大于等于2的个数+只有2个质数因子大于等于2的个数−...ans=n-只有一个质数因子次数大于等于2的个数+只有2个质数因子大于等于2的个数-...ans=n−只有一个质数因子次数大于等于2的个数+只有2个质数因子大于等于2的个数−...
然后这个东西跟莫比乌斯函数是一样的啊。
因此我们线性筛预处理莫比乌斯函数来当容斥系数。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5;
int n,m,pri[N],mu[N],tot=0,k;
bool vis[N];
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void init(){
mu[1]=1;
for(ri i=2;i<=100000;++i){
if(!vis[i])pri[++tot]=i,mu[i]=-1;
for(ri j=1;j<=tot&&i*pri[j]<=100000;++j){
vis[i*pri[j]]=1;
if(!(i%pri[j])){mu[i*pri[j]]=0;break;}
mu[i*pri[j]]=-mu[i];
}
}
}
inline bool check(ll x){
int sum=0;
for(ll i=1,up=sqrt(x);i<=up;++i)sum+=mu[i]*(x/(i*i));
return sum>=k;
}
int main(){
init();
ll l,r,ans;
for(ri tt=read();tt;--tt){
k=read();
l=1,ans=r=k*2;
while(l<=r){
ll mid=l+r>>1;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans<<'\n';
}
return 0;
}