polyd计数——pku2409

#include<stdio.h>
#include<math.h>
__int64 gcd(int a,int b)
{
    if(b==0)return a;
    else gcd(b,a%b);
}

int main()
{
    int c,n;
    while(scanf("%d%d",&c,&n),c&&n)
    {
        __int64 add=0;
        int i;
        
        for(i=1;i<=n;i++)
        {
            add+=(__int64)pow(c*1.0,gcd(n,i)*1.0);
        }
        
        if(n&1) //翻转的情况
            add+=(__int64)pow(c*1.0,(n+1)/2*1.0)*n;
        else
        {
            add+=(__int64)pow(c*1.0,(n+2)/2*1.0)*(n/2);
            add+=(__int64)pow(c*1.0,(n/2)*1.0)*(n/2);
        }
        
        printf("%I64d\n",add/n/2);
    }
}