6567번: Let it Bead

https://www.acmicpc.net/problem/6567


https://en.wikipedia.org/wiki/Necklace_(combinatorics)#Number_of_bracelets


포여열거정리를 이용한다.

#include<cstdio>
int pi(int x) {
    int r = x;
    for (int i = 2; i*i <= x; i++) {
        if (x%i == 0) r -= r / i;
        while (x%i == 0) x /= i;
    }
    return r - (x > 1)*r / x;
}
int pow(int x, int y) {
    if (!y) return 1;
    int r = pow(x, y / 2);
    return r*r*(y & 1 ? x : 1);
}
int c, s;
int main() {
    while (scanf("%d %d", &c, &s) && c) {
        int t = 0;
        for (int i = 1; i <= s; i++)
            if (s%i == 0) t += pi(i)*pow(c, s / i);
        printf("%d\n", (t / s + (s & 1 ? pow(c, s / 2 + 1) : (c + 1)*pow(c, s / 2) / 2)) / 2);
    }
    return 0;
}