1 int phi[5*K];
2 void init(int k)
3 {
4 phi[1]=1;
5 for(int i=2;i<k;i++) if(!phi[i])
6 for(int j=i;j<k;j+=i)
7 {
8 if(!phi[j]) phi[j]=j;
9 phi[j]=phi[j]/i*(i-1);
10 }
11 }
12 int euler(int x)
13 {
14 int ans=x;
15 for(int i=2;i*i<=x;i++)
16 if(x%i==0)
17 {
18 ans=ans/i*(i-1);
19 while(x%i==0) x/=i;
20 }
21 if(x>1)
22 ans=ans*x/(x-1);
23 return ans;
24 }