uva 10294 Arif in Dhaka (First Love Part 2) （Polya定理）

https://vjudge.net/problem/UVA-10294

题意：

用n颗k种颜色的珠子，分别能构成多少种项链和手镯

项链：旋转看作相同

手镯：旋转和翻转看作相同

利用Polya定理求等价类个数

旋转：

设旋转i颗珠子的间距（0<=i<n），那么（0 ，i，2i……）构成一个循环。这个循环的长度是n/gcd(i,n)。

证明：

设x经过最少p次旋转之后回到原处

即x+p*i = x (mod n)

p*i = 0 (mod n)

即 n | p*i

又因为 i | p*i，且要p最小

所以 p*i = lcm(n,i)

即 p*i=n*i/gcd(n,i) ，即p=n/gcd(n,i)

又因为每个循环长度一样，所以 循环个数有gcd(n,i)个。

由Polya定理可得，不动点个数有 ∑ k^(gcd(n,i))  i∈[0,n-1]

翻转：

要按n分奇偶讨论

n是奇数：

一共有n条对称轴，每条对称轴形成(n-1)/2个长为2的循环和1个长为1的循环，即一共(n+1)/2个循环

不动点个数有 n*k^((n+1)/2)

n是偶数：

有n/2条沿珠子的对称轴和n/2条在两颗珠子之间的对称轴

第一种对称轴形成n/2-1个长为2的循环和2个长为1的循环，共n/2+1个

第二种对称轴形成n/2个长为2的循环

不动点个数一共有 n/2 * ( k^(n/2+1) + k^(n/2) )

所以项链有∑ k^(gcd(n,i)) / n 个

手镯有  [ ∑ k^(gcd(n,i)) + n*k^((n+1)/2) ] / 2n  或者   [ ∑ k^(gcd(n,i)) + n/2 * ( k^(n/2+1) + k^(n/2) ) ] / 2n 个

#include<bits/stdc++.h>

using namespace std;

long long pw[52];

int main()
{
    int n,k;
    long long s1,s2;
    while(~scanf("%d%d",&n,&k))
    {
        pw[0]=1;
        for(int i=1;i<=n;++i) pw[i]=pw[i-1]*k;
        s1=0;
        for(int i=0;i<n;++i) s1+=pw[__gcd(n,i)];
        printf("%lld ",s1/n);
        if(n&1) s2=n*pw[n+1>>1];
        else s2=n/2*(pw[n/2+1]+pw[n/2]);
        printf("%lld
",(s1+s2)/2/n);
    }    
}