let it bead(polya).cpp

杭电acm解题报告2001---2099.

//Necklace of Beads是他的特殊情况
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int s,c;

int gcd(int x,int y) 
{
    if(x > y) {
        std::swap(x,y);
    }
    while(x) {
        int t = x;
        x = y % x;
        y = t;
    }
    return y;
}

__int64 f(__int64 m, __int64 n)
{
	__int64 t = 1;
	if(m == 0) {
		return 1;
	}
	while(m > 1) {
		if(m%2) {
			t *= n;
		}
		n *= n;
		m /= 2;
	}
	return __int64(t*n);
}

int main()
{
	int i;
	__int64 sum;
	while(scanf("%d %d", &c,&s)) {
		if(s==0 && c==0) {
			break;
		}
		int g = s+s;
		sum = 0;
		if(s%2) {
			sum += s*f(1 + s/2, c);
		}
		else {
            sum += s/2*(c+1)*f(s/2, c);
        }
		sum += f(s, c);
        for(i=1;i<s;i++) {
            sum += f( gcd(i,s), c);
        }
		printf("%I64d\n", sum / g);
	}
}