题目描述
求A^B的因子之和。(A和B范围5e7)
样例
输入:
2 3
输出:
15
解释:
2^3=8 1+2+4+8=15
算法
(简单数论) $O(√A+logA*logB)$
先把A分解成A=p1^x1p2^x2…pi^xi的形式。
设A的因子和为f(A),显然有
f(A)=(1+p1+p1^2+…+p1^x1)f(p2^x2…pi^xi)
=f(A/(p1^x1))*(p1^(x1+1)-1)/(p1-1)
由于A^B的因子种类和A相同,因子的幂为原来的B倍,因此套用上面的推论即可。
按这个方法递归即可。
时间复杂度
预处理A的所有因子,复杂度O(√A)
对于每个因子计算pi^(xi*b),复杂度为O(logB),共有不超过O(logA)个因子。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >v;
const int mod = 9901;
long long power(long long a,long long b){ //快速幂
long long res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
long long inv(long long x){ //逆元
return power(x,mod-2);
}
long long res;
long long f(long long a,long long b,long long i){
long long sum=(power(v[i].first,v[i].second*b+1)+mod-1)*inv(v[i].first-1)%mod;
//此为等比数列求和,逆元即除法
if(a==1)return 1;
int j;
long long t=1;
for(j=0;j<v[i].second;j++){
t*=v[i].first;
}
return f(a/t,b,i+1)*sum%mod; //递归调用,计算下一个素因子
}
int main(){
long long a,b,i;
cin>>a>>b;
if(a==0){cout<<0;return 0;} //特判特解
if(b==0){cout<<1;return 0;}
long long p=a;
for(i=2;i*i<=p;i++){
if(p%i==0){
int cnt=0;
while(p%i==0)p/=i,cnt++;
v.push_back({i,cnt});
}
}
if(p!=1)v.push_back({p,1});
cout<<f(a,b,0);
}