POJ 1286-Necklace of Beads

发表于 | 分类于 ， |

题目链接

POJ 1286 Necklace of Beads

题解

数据范围,不需要推式子
两种置换，旋转与反转
对于旋转置换,共有n种置换,跨度为k的置换轮换的个数为gcd(k,n)
对与反转置换
->当n为奇数是有种置换,每种置换包含n/2+1种轮换。
->当n是偶数时,如果对称轴过珠子,则存在n/2种置换，每种置换包含n/2种轮换
如果对称轴不过珠子,则存在n/2种置换，每种置换包含n/2+1种轮换
polay定理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cmath>
#include<cstdio>
#include<algorithm>
using std::__gcd;
#define LL long long
LL ans;
int main() {
    int n;
	while(scanf("%d",&n)==1) {
        if(n==-1) break;
		if(!n){puts("0");continue;}
		ans=0;
        for(int i=1;i<=n;i++)
			ans+=pow((LL)3,__gcd(n,i));
        if(n&1)
          ans+=pow(3,(n+1)/2)*n;
        else {
           ans+=pow(3,n/2+1)*(n/2);
           ans+=pow(3,n/2)*(n/2);
        }
        printf("%lld\n",ans/(2*n));
    }
    return 0;
}