UVa 10294 项链和手镯（polya）

题意：

手镯可以翻转，但项链不可以。输入n和t，输出用t种颜色的n颗珠子能制作成的项链和手镯的个数。

思路：

经典等价类计数问题。

对应题目的翻转问题，分奇偶讨论。

奇数时，如题图右，对称轴是一个珠子到圆心的连线，一共n条。选定对称轴后，对称轴上的一个珠子构成一个循环，其他n-1个珠子分别以对称轴对称构成(n-1)/2个循环，所以循环节的个数是 1 + (n – 1) / 2 = (n + 1) / 2 。

偶数时，如题图左，对称轴可能是两个珠子的连线，一共 n / 2条。选定对称轴后，对称轴上的两个珠子构成两个循环，其他n-2个珠子分别以对称轴对称构成(n-2)/2个循环；对称轴还可能是两个珠子的中点和圆心的连线，所有珠子两两对称，构成n / 2 个循环。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 using namespace std;
10 
11 typedef long long LL;
12 const int maxn=50+5;
13 
14 int n,t;
15 
16 int gcd(int a,int b)
17 {
18     return b==0?a:gcd(b,a%b);
19 }
20 
21 int main()
22 {
23     //freopen("D:\input.txt","r",stdin);
24     LL p[maxn];
25     while(scanf("%d%d",&n,&t)==2)
26     {
27         p[0]=1;
28         for(int i=1;i<=n;i++)  p[i]=p[i-1]*t;   //计算出t的n次方
29 
30         LL a=0;
31         for(int i=0;i<n;i++)  a+=p[gcd(i,n)];
32 
33         LL b=0;
34         if(n&1)  b=p[(n+1)/2]*n;
35         else  b=(p[n/2+1]+p[n/2])*n/2;
36         printf("%lld %lld
",a/n,(a+b)/2/n);
37     }
38     return 0;
39 }