poj 1286 Necklace of Beads

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

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

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

对应题目的旋转问题，直接套用现成结论。

一共n个置换，第i个置换的循环节的个数为gcd(n, i)。证明详见《挑战程序设计竞赛(第2版)》P302：

有了循环节，接下来只要将循环节数c作为幂求m^c即可。值得注意的是，同时考虑了旋转和翻转后，置换群的个数应当是2n。

#include<iostream> #include<math.h> #include<cstdio> #include<stdlib.h> #include<cstring> using namespace std; #define N 100010 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } long long pow1(long long m,int n) { long long sum=1; while(n>0) { if(n&1)sum*=m; m*=m; n/=2; } return sum; } int main() { int n; while(~scanf("%d",&n)) { long long count=0; if(n==-1)break; if(n==0){puts("0");continue;} for (int i = 1; i <= n; ++i) count += pow1(3, gcd(i, n));//计算珠子翻转 if (n & 1)//珠子旋转 count += n * pow1(3, n / 2 + 1); else count += n / 2 * (pow1(3, n / 2 + 1) + pow1(3, n / 2)); count /= n * 2; cout<<count<<endl; } return 0; }