polya定理 poj2409 Let it Bead

很经典的一道polya定理的题目，，以前看到这种具有对称性求个数的题目完全没法动。学了polya定理就能愉快的玩耍了。
polya定理很容易用，，大概就是一个这样的规律，先把所有的变换后颜色不变的情况写出来，比如这题就是：


1.如果旋转1下，前后颜色都不变
2.如果旋转2下，前后颜色都不变
........
n.如果旋转n下，前后颜色都不变
如果n是奇数，且对着每条角平分线对折，前后颜色都不变
如果n是偶数
  --|   如果对着每条角平分线对折，前后颜色都不变
  --|   如果对着边的中垂线对折，前后颜色都不变


把这些情况的数量都算出来，然后相加，除以总情况数，，就是答案了

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2000 + 5;LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL power(LL a, LL b) {LL ret = 1;while(b) {if(b & 1) ret *= a;a *= a;b >>= 1;}return ret;
}int main() {int m, n;//freopen("input.txt","r",stdin);while(~scanf("%d%d", &m, &n), m + n) {LL ans = 0;for(int d = 1; d <= n; d++) {ans += power(m, gcd(n, d));}if(n % 2 == 0) {ans += n / 2 * power(m, n / 2);ans += n / 2 * power(m, (n + 2) / 2);}else{ans += n * power(m, (n + 1) / 2);}printf("%I64d\n", ans / n / 2);}return 0;
}