POJ1286NecklaceofBeads

1 /*by SilverN*/
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #define LL long long
9 using namespace std;
10 int read(){
11 int x=0,f=1;char ch=getchar();
12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
14 return x*f;
15 }
16 LL phi(int x){
17 int m=sqrt(x+0.5);
18 LL res=x;
19 for(int i=2;i<=m;i++)
20 if(x%i==0){
21 res=res/i*(i-1);
22 while(x%i==0)x/=i;
23 }
24 if(x>1)res=res/x*(x-1);
25 return res;
26 }
27 int n;
28 int gcd(int a,int b){
29 return (!b)?a:gcd(b,a%b);
30 }
31 LL ksm(LL c,LL k){
32 LL res=1;
33 while(k){
34 if(k&1)res=res*c;
35 c*=c;
36 k>>=1;
37 }
38 return res;
39 }
40 int main(){
41 int i,j;
42 while(1){
43 n=read();
44 if(n==-1)break;
45 if(!n){
46 cout<<0<<endl;
47 continue;
48 }
49 LL ans=0;
50 for(i=1;i<=n;i++){
51 if(n%i==0)ans+=ksm(3,i)*phi(n/i);
52 }
53 if(!(n&1)){
54 ans+=ksm(3,n/2)*n/2;
55 ans+=ksm(3,n/2+1)*n/2;
56 }
57 else ans+=ksm(3,(n+1)/2)*n;
58 ans/=2*n;
59 cout<endl;
60 }
61 return 0;
62 }