AcWing 97. 约数之和
原题链接
中等
作者:
redial
,
2024-03-18 08:16:08
,
所有人可见
,
阅读 12
算法1
(递归,分解质因数)
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int A,B;
ll ans;
int primes[100010];//存放质因子
int k[100010];//质因子primes[i]的数量
int m=0;//质因子种类数
void divide(int x)//将x分解质因数,并计算数量
{
for(int i=2;i<=x/i;i++)
{
if(x%i==0)
{
primes[++m]=i;
int num=0;
while(x%i==0) x/=i,num++;
k[m]=num;
}
}
if(x>1) primes[++m]=x,k[m]=1;
}
ll qmi(int a,int b)//返回a^b%9901
{
ll res=1;
while(b)
{
if(b&1) res=res*a%9901;
b>>=1;
a=(ll)a*a%9901;
}
return res;
}
ll sum(int p,ll k)//求(p1^0+p1^1+……+p1^k1),递归实现
{
if(k==0) return 1;
if(k%2==0) return ((qmi(p,k/2)+1)*sum(p,k/2-1)+qmi(p,k))%9901;
else return ((qmi(p,(k+1)/2)+1)*sum(p,(k-1)/2))%9901;
}
//求A^B的约数之和,并对9901取模
//思路:求约数之和的公式为:sum=(p1^0+p1^1+……+p1^k1)*(p2^0+p2^1+……+p2^k2)*……*(pn^0+pn^1+……+p2^kn)
//其中p1~pn为所有质因子(互不相同),k1~kn分别对应每种质因子的个数
//对A分解质因数,若A的其中一个质因子pi的个数为ki,那么易得A^B的质因子pi的个数应为ki*B
int main()
{
cin>>A>>B;
divide(A);
ll res=1;
for(int i=1;i<=m;i++)
{
res=res*sum(primes[i],(ll)B*k[i])%9901;
}
if(A==0)//A=0时,A^B=0,0的约数之和仍为0,需要特判
{
cout<<0;
return 0;
}
cout<<res;
return 0;
}