求2014^X 因子和

之前千辛万苦发现了可以先把2014拆了，然而对于167这么大的数还是束手无策T^T

董学姐说多写几个找规律==然并卵，网上搜出了积性函数，也不会==直到看了苟神的博客http://blog.csdn.net/acdreamers/article/details/8220787逆元求解orz

再附上我小伙伴的博客http://blog.csdn.net/theArcticOcean/article/details/47207799

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;
const int N = 10005;
const int MOD = 29;

bool prime[N];
int p[N];
int cnt;

void isprime()
{
    cnt = 0;
    memset(prime,true,sizeof(prime));
    for(int i=2; i<N; i++)
    {
        if(prime[i])
        {
            p[cnt++] = i;
            for(int j=i+i; j<N; j+=i)
                prime[j] = false;
        }
    }
}

LL power(LL a,LL b)
{
    LL ans = 1;
    a %= MOD;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % MOD;
            b--;
        }
        b >>= 1;
        a = a * a % MOD;
    }
    return ans;
}

LL sum(LL a,LL n)
{
    if(n == 0) return 1;
    LL t = sum(a,(n-1)/2);
    if(n & 1)
    {
        LL cur = power(a,(n+1)/2);
        t = (t + t % MOD * cur % MOD) % MOD;
    }
    else
    {
        LL cur = power(a,(n+1)/2);
        t = (t + t % MOD * cur % MOD) % MOD;
        t = (t + power(a,n)) % MOD;
    }
    return t;
}

void Solve(LL A,LL B)
{
    LL ans = 1;
    for(int i=0; p[i]*p[i] <= A; i++)
    {
        if(A % p[i] == 0)
        {
            int num = 0;
            while(A % p[i] == 0)
            {
                num++;
                A /= p[i];
            }
            ans *= sum(p[i],num*B) % MOD;
            ans %= MOD;
        }
    }
    if(A > 1)
    {
        ans *= sum(A,B) % MOD;
        ans %= MOD;
    }
    cout<<ans<<endl;
}

int main()
{
    LL A,B;
    isprime();
    while(cin>>B){
        if(B==0) break;
        Solve(2004,B);
    }
    return 0;
}