大意：求A^B的所有因子之和，并对其取模 9901再输出
（这题又调了半天，把n和项数弄混了QAQ）
根据算数基本定理：A=(p1^k1)*(p2^k2)*(p3^k3)*...*(pn^kn) （pi为素数）
则A的所有因子之和Sum=(1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)
那么A^B = p1^(k1*B) * p2^(k2*B) * p3^(k3*B) *...* pn^(kn*B)
所以Sum=[1+p1+p1^2+...+p1^(a1*B)] * [1+p2+p2^2+...+p2^(a2*B)] *...* [1+pn+pn^2+...+pn^(an*B)]
用分治求等比数列1+pi+pi^2+pi^3+...+pi^n：
（1）若n为奇数（有偶数项）则：
1 + p + p^2 + p^3 +...+ p^n
= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))
= (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))
（2）若n为偶数（有奇数项）则:
1 + p + p^2 + p^3 +...+ p^n
= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)
= (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);
可以递归求解
#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register int
#define ll long long
const int mod=;
using namespace std;
int a,b,tot,ans=;
int pm[],cnt[]; inline ll q_pow(ll a,ll p)
{
if(a==) return ;
R ret=; a%=mod;
for(;p;p>>=,(a*=a)%=mod) if(p&) (ret*=a)%=mod;
return ret;
} ll sum(ll a,ll c)
{
if(c==) return ;
if(c&) return ((+q_pow(a,(c>>)+))%mod*sum(a,(c>>))%mod)%mod;
return ((+q_pow(a,(c>>)+))%mod*sum(a,(c-)>>)+q_pow(a,c>>)%mod)%mod;
} int main()
{
scanf("%d%d",&a,&b);
for(R i=;i*i<=a;i+=(i&?:))
if(a%i==)
{
pm[++tot]=i;
while(a%i==) cnt[tot]++,a/=i;
}
if(a!=) pm[++tot]=a,cnt[tot]++;//要判断一下A本身是不是素数
for(R i=;i<=tot;i++) ans=(ans*(sum(pm[i],cnt[i]*b)%mod))%mod;
printf("%d\n",ans);
}
如有错误，恳请您指正（我太菜了）；如有不理解，可留言，我会尽量回复。。。（高中生(逃)。。）
by Jackpei 2019.2.25