求 \(A^B\) 的约数和模 MOD

对 A 质因子分解 P1^k1*P2^k2….P^kn

A^B 即指数对应部分乘以 B

对于每个 P 都有 (1+P^1+P^2+…+P^ki) 的选择

连乘每一个 P 的等比数列之和即可

这里用了分治法，我觉得有必要记一下，不然推错就麻烦了

奇数部分 sum(p,c)=(1+p^(c+1»1))sum(p,c-1»1)

偶数部分 sum(p,c)=(1+p^(c»1))sum(p,c/2-1)+p^c

/*H E A D*/
inline int mod(ll a){
    return a%MOD;
}
int fpw(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=mod(ans*a);
        a=mod(a*a);
        n>>=1; 
    }
    return mod(ans);
    
}
int sum(int p,int n){
    if(n==0)return 1;
    if(n&1) return mod(mod(1+fpw(p,n+1>>1))*mod(sum(p,n-1>>1)));
    else return mod(mod(1+fpw(p,n>>1))*mod(sum(p,(n>>1)-1))+mod(fpw(p,n)));
}
ll n,cnt;
ll prime[maxn],num[maxn];
void chai(ll a){
    cnt=0;
    memset(num,0,sizeof num);
    memset(prime,0,sizeof prime);
    for(ll i = 2; i*i <= a; i++){
        if(a%i==0){
            cnt++;
            prime[cnt]=i;num[cnt]++;
            a/=i;
            while(a%i==0){
                num[cnt]++;
                a/=i;
            }
        }
    }
    if(a>1){
        cnt++;
        prime[cnt]=a;
        num[cnt]=1;
    }
}
int main(){
    ll a,b;
    while(~lin(a)){
        b=read();
        chai(a);
        rep(i,1,cnt) num[i]*=b;
//      rep(i,1,cnt) cout<<i<<" "<<prime[i]<<" "<<num[i]<<endl;
        ll ans=1;
        rep(i,1,cnt){
            int tmp=sum(prime[i],num[i]);
            ans=mod(ans*mod(tmp));
        }
        println(ans);
    }
    return 0;
}