| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7763 | Accepted: 3247 |
Description
Input
Output
Sample Input
4 5 -1
Sample Output
21 39
公式是这样子的：
p是颜色数，这里等于3，可以发现这2*n个置换形成了置换群，满足了群的封闭性。
那么只要对于每个置换找不动点就好了…… http://www.cnblogs.com/TenderRun/p/5656038.html 循环的部分和这题类似
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 long long pow[30],phi[30],n,ans; 6 long long Gcd(long long a,long long b){ 7 return b?Gcd(b,a%b):a; 8 } 9 int main(){ 10 pow[0]=1; 11 for(int i=1;i<=24;i++) 12 pow[i]=pow[i-1]*3; 13 for(int i=1;i<=24;i++) 14 for(int j=i;j>=1;j--) 15 if(Gcd(i,j)==1)phi[i]+=1; 16 while(scanf("%lld",&n)!=EOF&&n!=-1){ 17 if(n==0){printf("0\n");continue;} 18 for(int d=1;d<=n;d++) 19 if(n%d==0)ans+=phi[n/d]*pow[d]; 20 if(n%2)ans=(ans+n*pow[(n+1)/2])/2/n; 21 else ans=(ans+n/2*(pow[n/2+1]+pow[n/2]))/2/n; 22 printf("%lld\n",ans);ans=0; 23 } 24 } 25
数学计数原理（Pólya）：POJ 1286 Necklace of Beads
原文：http://www.cnblogs.com/TenderRun/p/5789609.html