#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;

int gcd(int x,int y){
    return y ? gcd(y,x%y) : x;
}

int main()
{
    int n,m;
    LL ans;
    while(scanf("%d%d",&m,&n) != EOF){
        if(m==0 && n == 0) break;
        ///翻转
        if(n & 1){
            ans = pow(m ,n/2+1) * n;
        }
        else{
            ans = pow(m ,n/2+1)* (n/2)
            + pow(m,n/2) * (n/2);
        }
        ///旋转
        for(int i = 1; i <= n; i++){
            ans += pow(m,gcd(n,i));
        }
        printf("%lld\n",ans/(n*2));
    }
    return 0;
}

我等弱菜，我真的是很难看懂polya定理啊卧槽。。。看不懂啊看不懂啊 

还是不看好吧啦                        orz...           数学什么的，给跪了！

poj 2409 polya定理