POJ 2409 Let it Bead

RT.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long c,s,ans=0;
long long f_pow(long long x,long long y)
{
    long long base=x,ans=1;
    while (y)
    {
        if (y&1) ans*=base;
        base*=base;
        y>>=1;
    }
    return ans;
}
long long gcd(long long a,long long b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
int main()
{
    for (;;)
    {
        scanf("%lld%lld",&c,&s);
        if ((!c) && (!s)) break;
        if ((!c) || (!s)) {printf("0
");continue;}
        ans=0;
        for (long long i=0;i<=s-1;i++)
            ans+=f_pow(c,gcd(i,s));
        if (s&1) ans+=s*f_pow(c,s/2+1);
        else ans+=s/2*f_pow(c,s/2+1)+s/2*f_pow(c,s/2);
        ans/=2*s;
        printf("%lld
",ans);
    }
    return 0;
}