Let it Bead

// File Name: poj2409.cpp  
// Author: bo_jwolf  
// Created Time: 2013年10月08日 星期二 14:31:08  
  
#include<vector>  
#include<list>  
#include<map>  
#include<set>  
#include<deque>  
#include<stack>  
#include<bitset>  
#include<algorithm>  
#include<functional>  
#include<numeric>  
#include<utility>  
#include<sstream>  
#include<iostream>  
#include<iomanip>  
#include<cstdio>  
#include<cmath>  
#include<cstdlib>  
#include<cstring>  
#include<ctime>  
  
#define INT long long int  
  
using namespace std;  
INT 易做图( INT a, INT b){  
    return b == 0? a: 易做图( b, a % b );  
}  
  
INT c, s;  
INT polya(){  
    INT ans = 0;  
    for( INT i = 0; i < s; ++i ){  
        ans += (INT)pow( 1.0 * c, 易做图( s, i ) );  
    }  
    if( s % 2 ){  
        ans += s * ( INT )pow( 1.0 * c, ( s / 2 + 1 ) );  
    }  
    else{  
        ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 );  
        ans += s / 2 * ( INT )pow( 1.0 * c, s / 2 + 1 );  
    }  
    return ans / 2 / s;  
}  
  
int main(){  
    INT ans;  
    while( scanf( "%lld%lld", &c, &s ) != EOF ){  
            if( !c && !s )  
                break;  
            ans = polya();  
            printf( "%lld\n", ans );  
    }  
return 0;  
}