Let it Bead

大意：给你m种颜色，n个珠子串起来，旋转跟反转相同算相同，问有多少种不同的涂色组合方式。

思路：Polya的简单应用。

/*************************************************************************
    > File Name: POJ2409.cpp
    > Author: GLSilence
    > Created Time: 2014年07月29日 星期二 22时56分58秒
 ************************************************************************/

#include
  
   
#include
   
     #include 
    
      using namespace std; #define LL long long LL GCD(LL a, LL b){ return b ? GCD(b, a%b) : a; } int n, m; int main() { while(~scanf("%d%d", &m, &n) && (n||m)){ LL ans = 0; for(int i = 1; i <= n; ++i){ ans += (LL)pow(m*1.0, GCD(n, i)); } if(n%2){ ans += n*(LL)pow(m*1.0, n/2+1); } else { ans += n/2*(LL)pow(m*1.0, n/2); ans += n/2*(LL)pow(m*1.0, n/2+1); } printf("%lld\n", ans/2/n); } return 0; }