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;
}