hdu1787GCD Again
4268 ワード
リンク:http://acm.hdu.edu.cn/showproblem.php?pid=1787
赤果果果のオーラ関数;
View Code
赤果果果のオーラ関数;
View Code
1 #include <iostream>
2 using namespace std;
3 // x=p1^e1*p2^e2~~~pn^en
4 //phi(x)=(p1-1)*p1^(e1-1)*(p2-1)*p2^(e2-1)~~~(pn-1)*pn^(en-1)
5 int phi(int m)
6 {
7 int i,s=1;
8 for(i=2;i*i<=m;i++) {
9 if(m%i==0){
10 m/=i;
11 s*=i-1;
12 while(m%i==0) {
13 m/=i;
14 s*=i;
15 }
16 }
17 }
18 if(m>1)
19 s*=m-1;
20 return s;
21 }
22 int main()
23 {
24 int m;
25 while(cin>>m && m)
26 cout<<m-1-phi(m)<<endl;
27 return 0;
28 }