POJ 1845 二分+素因子分解

题意：求a^b的因子的和。

对a进行素因子分解a=p1^k1*p2^k2*...*pn^kn则根据成型函数的性质有s=(1+p1+p1^2+p1^3...p1^(k1*b))*....()

等比数列直接二分求前n项和即可。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 30000
bool isprime[maxn];
int prime[maxn],nprime;
typedef long long int64;
int64 modmult(int64 a,int64 b,int64 n)//a*b%n
{
    a%=n;
    int64 ret;
    for(ret=0; b; a=(a<<1)%n,b>>=1)
        if(b&1)
            ret=(ret+a)%n;
    return ret;
}
int64 modular(int64 a,int64 b,int64 n)//renturn a^b%n
{
    int64 ans=1;
    a%=n;
    while(b)
    {
        if(b&1)
            ans=modmult(ans,a,n),b--;
        b>>=1;
        a=modmult(a,a,n);
    }
    return ans;
}
void getprime()
{
    memset(isprime,1,sizeof(isprime));
    long long i,j;
    nprime=0;
    for(i=2; i<maxn; i++)
        if(isprime[i])
        {
            prime[nprime++]=i;
            for(j=i*i; j<maxn; j+=i)
                isprime[j]=0;
        }
}
long long fac[100][2],tol;
void getfac(int n)
{
    tol=0;
    int x=n;
    memset(fac,0,sizeof(fac));
    for(int i=0; prime[i]*prime[i]<=n; i++)
        if(x%prime[i]==0)
        {
            fac[tol][0]=prime[i];
            while(x%prime[i]==0) fac[tol][1]++,x/=prime[i];
            tol++;
        }
    if(x>1)
        fac[tol][0]=x,fac[tol++][1]++;
}
long long getsum(long long a,long long k,long long m)
{
    if(k==1)
        return a%m;
    if(k&1)
        return (a+modmult(getsum(a,k/2,m),(a+modular(a,k/2+1,m))%m,m))%m;
    return modmult(getsum(a,k/2,m),1+modular(a,k/2,m),m);
}
int main()
{
    getprime();
    int a,b;
    long long ans;
    while(~scanf("%d%d",&a,&b))
    {
        if(a==1||b==0)
        {
            puts("1");
            continue;
        }
        ans=1;
        getfac(a);
        for(int i=0; i<tol; i++)
        {
            fac[i][1]*=b;
            ans=(ans*(getsum(fac[i][0],fac[i][1],9901)+1))%9901;
        }
        ans=(ans%9901+9901)%9901;
        printf("%d\n",ans);
    }
    return 0;
}