原来rotation的时候也会形成环的，环的数量等于Gcd(n,i),n为珠子的数目，i为旋转步长。
其他就没什么了，只是求最大公约数那一步只是感觉出来的，不知道该怎么证明。
#include<iostream>
using namespace std;
int pow(int c,int x)
{
int ans = 1;
for(int i=0;i<x;i++)
ans = ans * c;
return ans;
}
int Gcd(int a, int b)
{
return a == 0 ? b : Gcd(b % a, a);
}
int main()
{
int c,s;
int G;//表示置换群的大小
while(scanf("%d%d",&c,&s)!=EOF)
{
if(c==0&&s==0)
break;
G = s<<1;
int ans = pow(c,s);
//考虑rotation的情况
for(int i =1 ;i< s ;i ++)
ans += pow ( c , Gcd(s, i));
//分奇偶考虑reflection的情况
if(s&1)
ans += s*c*pow(c,(s-1)>>1);
else
{
ans += s/2 * pow(c,s/2);
ans += s/2 * c * c * pow(c,s/2-1);
}
printf("%d\n",ans/G);
}
return 0;
}