原來(lái)rotation的時(shí)候也會(huì)形成環(huán)的，環(huán)的數(shù)量等于Gcd(n,i),n為珠子的數(shù)目，i為旋轉(zhuǎn)步長(zhǎng)。
其他就沒什么了，只是求最大公約數(shù)那一步只是感覺出來(lá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;
}