【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_{f\in 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\n", ans / (s << 1));
}
return 0;
}