POJ 2409 Let it Bead（Polya定理）

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;

int gcd(int a,int b)
{
    return b > 0 ? gcd(b,a%b) : a ;
}
int main()
{
    int c,s ;
    while (scanf("%d %d", &c, &s) != EOF)
    {
        if(c == 0 && s == 0) break ;
        int sum = 0;
        for (int i = 1; i <= s; i++)
            sum += pow(c, gcd(i, s));
        if (s & 1)
            sum += s * pow(c, s / 2 + 1);
        else
            sum += s / 2 * pow(c, s / 2) + s / 2 * pow(c, s / 2 + 1);
        sum /= s * 2;
        printf("%d\n", sum);
    }
    return 0;
}