Let it Bead

大意：给你m种颜色，n个珠子串起来，旋转跟反转相同算相同，问有多少种不同的涂色组合方式。

思路：Polya的简单应用。

/*************************************************************************
    > File Name: POJ2409.cpp
    > Author: GLSilence
    > Created Time: 2014年07月29日 星期二 22时56分58秒
 ************************************************************************/

#include<stdio.h>
#include<iostream>
#include <math.h>
using namespace std;

#define LL long long

LL GCD(LL a, LL b){
    return b ? GCD(b, a%b) : a;
}

int n, m;

int main()
{
    while(~scanf("%d%d", &m, &n) && (n||m)){
        LL ans = 0;
        
        for(int i = 1; i <= n; ++i){
            ans += (LL)pow(m*1.0, GCD(n, i));
        }

        if(n%2){
            ans += n*(LL)pow(m*1.0, n/2+1);
        }
        else {
            ans += n/2*(LL)pow(m*1.0, n/2);
            ans += n/2*(LL)pow(m*1.0, n/2+1);
        }

        printf("%lld\n", ans/2/n);

    }

    return 0;
}