此题是赤裸裸的求欧拉函数,但是傻冒的用辗转想除法去求的,结果悲剧了,tle了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <stdio.h> int Ecluid (int N,int 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了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #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(); 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了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #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)){ ++friend_num; } } printf ("%d\n" ,friend_num+1 ); } return 0 ; }
最后痛定思痛,发现居然是赤裸裸的欧拉函数就可以解决,,尴尬,哎,只是把bit
1049 Relatives这道题的代码拿过来改了一下,瞬间AC!那个高兴哇大笑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #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 ; }