欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj 1286

程序员文章站 2024-03-16 15:43:34
...
polya定理的基础题目。置换群中有两种情况。
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
const int maxn=30;
LL pow[maxn];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    pow[1]=3;
    int i;
    for(i=2;i<=24;i++) pow[i]=pow[i-1]*(LL)3;
    int n;
    while(scanf("%d",&n)&&n!=-1)
    {
        if(n==0)
        {
            printf("%d\n",0);
            continue;
        }
        LL ans=0;
        for(i=0;i<n;i++) ans+=pow[gcd(i,n)];//情况一的不动点的个数
        if(n%2) ans+=(LL)n*pow[(n+1)/2];
        else ans+=(LL)(n/2)*(pow[n/2+1]+pow[n/2]);
        printf("%I64d\n",ans/2/n);
    }
    return 0;
}

转载于:https://www.cnblogs.com/lj030/archive/2013/05/05/3065554.html