【POJ 2409】Let it Bead

http://poj.org/problem?id=2409
Burnside引理：设(G)是(X)的置换群，而(mathcal{C})是(X)中一个满足下面条件的着色集合：对于(G)中所有的(f)和(mathcal{C})中所有的(mathbf{c})都有(f*mathbf{c})仍在(mathcal{C})中，则(mathcal{C})中非等价着色数(N(G,mathcal{C}))由下式给出：$$N(G,mathcal{C})=frac 1{|G|}sum_{fin G}|mathcal{C}(f)|$$
换言之，(mathcal{C})中非等价的着色数等于在(G)中的置换作用下保持不变的着色的平均数。
直接套用定理就可以了qwq

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int ipow(int a, int b) {
	int ret = 1, w = a;
	while (b) {
		if (b & 1) ret *= w;
		w *= w;
		b >>= 1;
	}
	return ret;
}

int c, s, ans, half;

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

int main() {
	while (~scanf("%d%d", &c, &s)) {
		if (c == 0 && s == 0) break;
		ans = 0;
		for (int i = 1; i <= s; ++i)
			ans += ipow(c, gcd(i, s));
		half = (s + 1) >> 1;
		if (s & 1)
			ans += s * ipow(c, half);
		else
			ans += (s >> 1) * (ipow(c, half) + ipow(c, half + 1));
		printf("%d
", ans / (s << 1));
	}
	return 0;
}