首页 > 代码库 > POJ 1286 Necklace of Beads(项链的珠子)
POJ 1286 Necklace of Beads(项链的珠子)
Necklace of Beads
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7874 | Accepted: 3290 |
Description
Beads of red, blue or green colors are connected together into a circular necklace of n beads ( n < 24 ). If the repetitions that are produced by rotation around the center of the circular necklace or reflection to the axis of symmetry are all neglected, how many different forms of the necklace are there?
Input
The input has several lines, and each line contains the input data n.
-1 denotes the end of the input file.
-1 denotes the end of the input file.
Output
The output should contain the output data: Number of different forms, in each line correspondent to the input data.
Sample Input
45-1
Sample Output
2139
/*Polya原理*/#include <cstdio>#include <iostream>using namespace std;long long aaaa(long long a,long long b){ long long res=1,tmp=a; while(b) { if (b&1) res*=tmp; tmp*=tmp; b>>=1; } return res;}int gcd(int a,int b) { return b==0?a:gcd(b,a%b);}int main(){ int n; while ( ~scanf("%d", &n) && n != -1) { long long a = 0, b = 0; for (int i=0;i<n;i++) { a+=aaaa(3,gcd(i,n)); } if (n&1) b=(long long)n*aaaa(3,(n+1)/2); else b=(long long)n/2*(aaaa(3,n/2+1)+aaaa(3,n/2)); if (n==0) printf("0\n"); else printf("%lld\n",(a+b)/2/n); } return 0;}
POJ 1286 Necklace of Beads(项链的珠子)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。