最裸的求莫比乌斯函数的题。1A。
http://oj.changjun.com.cn/problem/detail/pid/2395
1 #include<cmath> 2 #include<queue> 3 #include<cstdio> 4 #include<vector> 5 #include<cstdlib> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define N 10000010 10 #define RG register 11 #define inf 0x3f3f3f3f 12 #define Inf 99999999999999999LL 13 using namespace std; 14 typedef long long LL; 15 bool vis[N]; 16 int T,n,op,top,mu[N],sta[N],euler[N]; 17 inline int gi(){ 18 RG int x=0;RG bool flag=0;RG char c=getchar(); 19 while((c<'0'||c>'9')&&c!='-') c=getchar(); 20 if(c=='-') c=getchar(),flag=1; 21 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 22 return flag?-x:x; 23 } 24 inline void init(){ 25 mu[1]=euler[1]=1; 26 for (RG int i=2;i<N;++i){ 27 if(!vis[i]){ 28 mu[i]=-1; 29 euler[i]=i-1; 30 sta[++top]=i; 31 } 32 for (RG int j=1;j<=top&&i*sta[j]<N;++j){ 33 vis[i*sta[j]]=1; 34 if(i%sta[j]==0){ 35 mu[i*sta[j]]=0; 36 euler[i*sta[j]]=euler[i]*sta[j]; 37 break; 38 } 39 mu[i*sta[j]]=-mu[i]; 40 euler[i*sta[j]]=euler[i]*(sta[j]-1); 41 } 42 } 43 } 44 inline void work(){ 45 op=gi();n=gi(); 46 if(op==1) 47 printf("%d ",sta[n]); 48 if(op==2) 49 printf("%d ",mu[n]); 50 if(op==3) 51 printf("%d ",euler[n]); 52 } 53 int main(){ 54 freopen("2395.in","r",stdin); 55 freopen("2395.out","w",stdout); 56 init();T=gi(); 57 while(T--) work(); 58 fclose(stdin); 59 fclose(stdout); 60 return 0; 61 }