http://www.lydsy.com/JudgeOnline/problem.php?id=2440
看到loriex在研究莫比乌斯反演,我也跟着去学了学
耗费了一上午,刚化学课刚把这道题题解想懂了,随手做了下
其实就是莫比乌斯函数的意义
Orz loriex,到现在还是不会DZY loves math
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive Blog:http://willinglive.cf ************************************************/ #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) inline const int read() { int r=0,k=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1; for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0'; return k*r; } ///////////////////////////////////////////////// const int N=320000; int n,T; int prim[50000],mu[320010],cnt; bool flag[320010]; ///////////////////////////////////////////////// void get_prim_mu() { mu[1]=1; rep(i,2,N) { if(!flag[i]) prim[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt && i*prim[j]<=N;j++) { flag[i*prim[j]]=1; if(i%prim[j]==0) { mu[i*prim[j]]=0; break; } else mu[i*prim[j]]=-mu[i]; } } } inline bool check(LL m) { LL s=0; LL sq=(int)sqrt((double)m); rep(i,1,sq) s+=mu[i]*(m/(i*i)); return s<n; } ///////////////////////////////////////////////// void input() { T=read(); } void solve() { get_prim_mu(); while(T--) { n=read(); LL l=1,r=n*2,mid; while(l<r) { mid=l+r>>1; if(check(mid)) l=mid+1; else r=mid; } printf("%d\n",l); } } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(), solve(); return 0; }