学步园

  题意：n个珠子的项链和手镯，用t种颜色涂色，手镯可以翻转，问各有多少种不同的手镯和项链？

解析：

旋转：每移动i颗珠子，循环节为gcd（i，n），故ans1=sum（t^gcd(i,n)）,t为颜色种数；

翻转：奇：有n条对称轴，共（n+1）/2个循环节！　　ans2=n*t^(（n+1）/2)

　　　偶：1）穿过珠子有n/2条对称轴，有（n/2+1）个循环节！

　　　　　2）不穿过珠子也有n/2条对称轴，有n/2个循环节！　　ans2=n/2*(t^(n/2+1)+t^(n/2))

 Polya定理和Burnside 引理的第一题，开始公式推错了，一直wrong ，后来发现是因为后面的Polya计数没看，与循环数有关 ，即旋转的时候循环数=gcd（n，i）；

其中n为点数，i为旋转间隔

#include<iostream>
#include<cstdio>
using namespace std;

typedef  long long LL;

LL gcd(LL a,LL b)
{
   return b==0?a:gcd(b,a%b);
}

int main()
{
    int i;
    LL a,b,n,t;
    while(scanf("%lld%lld",&n,&t)==2&&n)
    {
       LL p[66]={0};
       p[1]=t;
       p[0]=1;
       for(i=2;i<=n;i++)
           p[i]=t*p[i-1];

        a=0;
       for(i=0;i<n;i++)
       {
          a+=p[gcd(n,i)];
       }

       if(n%2)
           b=n*p[(n+1)/2];
       else  b=n*(p[n/2+1]+p[n/2])/2;

       printf("%lld %lld\n",a/n,(a+b)/2/n);

    }
    return 0;
}