此题是赤裸裸的求欧拉函数,但是傻冒的用辗转想除法去求的,结果悲剧了,tle了。

    #include<stdio.h>
     
    int Ecluid(int N,int a){
    //求 N 和a的最大公约数	
    	if(N % a == 0)return a;
    	else{
    		N%=a;
    		Ecluid(a,N);
    	}
    }
     
    int main(){
    	int test_case,N,friend_num;
    	scanf("%d",&test_case);
    	while(test_case --){
    		scanf("%d",&N);
    		friend_num = 0;
    		for(int i = 2;i<N;++i){
    		   if(Ecluid(N,i)!=1){
    			++friend_num;
    		   }
    		}
    		printf("%d\n",N - friend_num - 1);
    	}
     
    	return 0;
    }

接着打了一张素数表的方法,然后一个一个的判断其公约数,结果还是大哭tle了。


    #include<stdio.h>
    #include<string.h>
     
    int prime[2000],prime_top = 0;
     
    void build_prime(){
    	int not_prime[20000];
    	memset(not_prime,0,sizeof(not_prime));
    	for(int i = 2;i<=17000;++i){
    		if(!not_prime[i]){
    			prime[prime_top++] = i;		
    		}
    		for(int j=0;i*prime[j]<=17000 && j<prime_top;++j){
    			not_prime[i*prime[j]] = 1;
    			if(i%prime[j] == 0){break;}
    		}
    	}
    }
     
    int main(){
    	
    	int test_case,N,not_new_friend_num;
    	build_prime();
    	//printf("%d %d\n",prime[prime_top - 1],prime_top);
    	scanf("%d",&test_case);
    	while(test_case --){
    		scanf("%d",&N);
    		not_new_friend_num = 0;
    		for(int i = 2;i < N;++i){
    			for(int j = 0;j < prime_top;++j){
    				if(N%prime[j] == 0 && i % prime[j] ==0){
    		   			++not_new_friend_num;
    					break;
    				}
    			}
    		}
    		
    		printf("%d\n",N - not_new_friend_num - 1);
    	}
    	return 0;
    }

然后实在不行百度一下,看到有人说用欧拉函数,我就居然想到了,phi(mn) = phi(m)*phi(n)的方法,却没想到是赤裸裸的欧拉函数,结果,还是tle了。


    #include<stdio.h>
     
      
    int Eu(int n){
        int ans = 1;
        for(int i = 2; i * i <= n;++i){  
            if(!(n%i)){  
                ans *= i - 1;  
                n /= i;  
                while(!(n%i)){  
                    ans *= i;n/=i;   
                }   
            }  
        }  
        if(n > 1){  
            ans *= n -1;  
        }  
        return ans;  
    }
    int main(){
    	
    	int test_case,N,friend_num;
    	scanf("%d",&test_case);
    	while(test_case --){
    		scanf("%d",&N);
    		friend_num = 0;
    		for(int i = 2;i<N;++i){
    		   if(Eu(i)*Eu(N)==Eu(N*i)){
    			//printf("%d\n",i);
    			++friend_num;
    		   }
    		}
    		printf("%d\n",friend_num+1);
    	}
    	return 0;
    }

最后痛定思痛,发现居然是赤裸裸的欧拉函数就可以解决,,尴尬,哎,只是把bit 1049 Relatives这道题的代码拿过来改了一下,瞬间AC!那个高兴哇大笑。


    #include <stdio.h>
    int ans;
    void Eu(int n){
    	for(int i = 2; i * i <= n;++i){
    		if(!(n%i)){
    			ans *= i - 1;
    			n /= i;
    			while(!(n%i)){
    				ans *= i;n/=i; 
    			} 
    		}
    	}
    	if(n > 1){
    		ans *= n -1;
    	}
    	return ;
    }
    int main(){
    	int n,test_case;
    	scanf("%d",&test_case);
    	while(test_case--){
    		scanf("%d",&n);
    		ans = 1;
    		Eu(n);
    		printf("%d\n",ans);
    	}
    	return 0;
    }