poj2409 Burnside引理 + Polya定理(圆)

/*
Time:2019.12.15
Author: Goven
type：Burnside引理 + Polya定理(圆)
ref:
https://www.cnblogs.com/AKCqhzdy/p/7593704.html
https://blog.csdn.net/lianai911/article/details/47804663
*/
#include<iostream>

using namespace std;

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

int quick_pow (int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main()
{
    int c, s;
    while (cin >> c >> s) {
        if (!c && !s) break;
        int res = 0;
        //旋转变换
        for (int i = 1; i <= s; i++) res += quick_pow(c, gcd(i, s)); 
        //翻转变换
        if (s & 1) {
            res += s * quick_pow(c, (s + 1) / 2);
        } 
        else {
            res += s / 2 * quick_pow(c, s / 2);
            res += s / 2 * quick_pow(c, s / 2 + 1);
        }
        res /= 2 * s;
        cout << res << endl;
    } 
    return 0;
}