Necklace of Beads(polya定理)

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 long long gcd(long long a,long long b)
 5 {
 6     return b?gcd(b,a%b):a;
 7 }
 8 int main()
 9 {
10     long long n;
11     while(~scanf("%lld",&n))
12     {
13         if (n==-1)
14             break;
15         if (n <= 0)
16         {
17             printf("0\n");
18             continue;
19         }
20         long long ans = 0;
21         for (int i = 0; i < n; i++)
22         {
23             ans+=pow(3,gcd(i,n));
24         }
25         if (n&1)
26             ans+=n*pow(3,n/2+1);
27         else
28         {
29             ans+=n/2*pow(3,n/2)+n/2*pow(3,n/2+1);
30         }
31         printf("%lld\n",ans/n/2);
32     }
33     return 0;
34 }

 1 #include <stdio.h>
 2 #include <math.h>
 3 long long gcd(long long a,long long b)
 4 {
 5     return b?gcd(b,a%b):a;
 6 }
 7 /*long long pow(long long a,long long b)
 8 {
 9     long long res = 1;
10     while(b)
11     {
12         if (b&1)
13             res*=a;
14         a*=a;
15         b>>=1;
16     }
17     return res;
18 }*/
19 int main()
20 {
21     int n,k;
22     while(~scanf("%d%d",&k,&n))
23     {
24         if (k==0&&n==0)
25             break;
26         long long ans = 0;
27         for (int i = 0; i < n; i++)
28         {
29             ans+=pow(k,gcd(i,n));
30         }
31         if (n&1)
32             ans+=n*pow(k,n/2+1);
33         else
34         {
35             ans+=n/2*pow(k,n/2)+n/2*pow(k,n/2+1);
36         }
37         printf("%lld\n",ans/n/2);
38     }
39     return 0;
40 }