poj_1845: Sumdiv

题目链接

先将A^B分解质因数，可以通过先分解A，再把对应的幂次*B。之后用下面这个式子求解就可以了

#include<vector>

#include<iostream>

using namespace std;

typedef long long LL;

const int mod=;

const int N=1e4+;

LL A,B;

bool not_prime[N+];

vector<int> prime;

void init()

{

    for(int i=;i<N;i++)

    {

        if(!not_prime[i])

        {

            prime.push_back(i);

            for(int j=i*i;j<N;j+=i)

                not_prime[j]=true;

        }

    }

}

LL qpow(LL x,LL n)

{

    LL ret=;

    for(;n;n>>=)

    {

        if(n&) ret=ret*x%mod;

        x=x*x%mod;

    }

    return ret;

}

LL sum(LL q,LL n)    //求首项为1，公比为q 的等比数列的前n项和

{

    if(n==) return ;

    LL ret=;

    LL ls=sum(q,n/);

    LL rs=ls*qpow(q,n/)%mod;

    ret=(ls+rs)%mod;

    if(n&) ret=(ret+qpow(q,n-))%mod;

    return ret;

}

LL cal(LL A,LL B)

{

    LL ret=;

    for(int i=;prime[i]*prime[i]<=A&&i<prime.size();i++)

    {

        if(A%prime[i]==)

        {

            int cnt=;

            while(A%prime[i]==) cnt++,A/=prime[i];

            ret=ret*sum(prime[i],cnt*B+)%mod;

        }

    }

    if(A>) ret=ret*sum(A,B+)%mod;

    return ret;

}

int main()

{

    init();

    while(cin>>A>>B)

        cout<<cal(A,B)<<endl;

}