题意：求A^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<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=;
const int N=1e5+;
int p[N],pr[N],cnt;
void init(){
for(int i=;i<N;i++){
if(!p[i]) pr[++cnt]=i;
for(int j=;j<=cnt&&i*pr[j]<N;j++){
p[i*pr[j]]=;
if(i%pr[j]==) break;
}
}
}
ll pow_m(ll a,ll b,ll m){
ll ans=;a%=m;
while(b){
if(b&)
ans=(ans*a)%m;
a=(a*a)%m;
b>>=;
}
return ans;
}
ll sum(ll p,ll n){
if(!n) return ;
if(n&){
return (sum(p,n/)*(+pow_m(p,n/+,mod)))%mod;
}
else{
return (sum(p,n/-)*(+pow_m(p,n/+,mod))+pow_m(p,n/,mod))%mod;
}
}
int main(){
ll a,b;
init();
while(~scanf("%lld%lld",&a,&b)){
ll ans=;
for(int i=;i<=cnt&&pr[i]*pr[i]<=a;i++){
if(a%pr[i]==){
int num=;
while(a%pr[i]==){
num++;
a/=pr[i];
}
ans=(ans*sum(pr[i],num*b))%mod;
}
}
if(a>){
ans=(ans*sum(a,b))%mod;
}
printf("%lld\n",ans);
}
return ;
}
第二种方法就是用等比数列求和公式，但是要用逆元。用如下公式即可(已知a|b)
我们来证明它，已知，证明步骤如下
在快速幂时的乘法会爆longlong，所以用快速乘
#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=;
const int N=1e5+;
int p[N],pr[N],cnt;
void init(){
for(int i=;i<N;i++){
if(!p[i]) pr[++cnt]=i;
for(int j=;j<=cnt&&i*pr[j]<N;j++){
p[i*pr[j]]=;
if(i%pr[j]==) break;
}
}
}
ll mul(ll a,ll b,ll m){
ll ans=;a%=m;
while(b){
if(b&)
ans=(ans+a)%m;
a=(a+a)%m;
b>>=;
}
return ans;
}
ll pow_m(ll a,ll b,ll m){
ll ans=;a%=m;
while(b){
if(b&)
ans=mul(ans,a,m);
a=mul(a,a,m);
b>>=;
}
return ans;
}
int main(){
ll a,b;
init();
while(~scanf("%lld%lld",&a,&b)){
ll ans=;
for(int i=;i<=cnt&&pr[i]*pr[i]<=a;i++){
if(a%pr[i]==){
int num=;
while(a%pr[i]==){
num++;
a/=pr[i];
}
ll M=(pr[i]-)*mod;
ans*=(pow_m(pr[i],num*b+,M)+M-)/(pr[i]-);
ans%=mod;
}
}
if(a>){
ll M=(a-)*mod;
ans*=(pow_m(a,b+,M)+M-)/(a-);
ans%=mod;
}
printf("%lld\n",ans);
}
return ;
}