题解 P1593 【因子和】
C_Cong
·
·
题解
博客传送门
题意简述：
求a^b的所有因子和
解题思路：
既然要求因子和，那我们必然要先分解质因数
根据整数的唯一分解定理，整数a进行质因数分解对应的式子唯一，有:
a = p_1^{k_1} * p_2^{k_2} *p_3^{k_3}* … * p_n^{k_n}
又因为本题要分解的是a^b，所以上面的式子又可以写成这样：
a^b= p_1^{k_1*b} * p_2^{k_2*b} *p_3^{k_3*b}* … * p_n^{k_n*b}
证明很简单，就是把上面第一个式子乘上b次即可得第二个式子
接下来我们要求的是因子和，
所以就有：
ans= (1+p_1^1 + p_1^2 +p_1^3+ … + p_1^{k_1*b})*(1+p_2^1 + p_2^2 +p_2^3+ … + p_1^{k_2*b})*...*(1+p_n^1 + p_n^2 +p_n^3+ … + p_n^{k_n*b})
对于上面的式子是不是有点熟悉？
对，你没有看错，就是等比数列之间的乘积
根据等比数列求和公式：
sum=\frac{p^{n}-1}{p-1}
我们就能求出各数列的和，
对于p^{n+1}，我们用快速幂求
又因为本题要求的答案要对9901取模
故我们又可以通过逆元将除p-1转化为乘p-1的逆元
接下来要求逆元，根据定义，在mod\ p的意义下，对于一个整数a，有：
a*x≡1(mod\ p)
注意此处的$a,p$均与上文的意义不同，仅作为公式中的未知数
当$a,p$不互质时，逆元不存在，即上面的式子要满足：
$$gcd(a,p)=1$$
那么这个$x$怎么求？
那我们再引入一个定理，费马小定理：
假如$a$是一个整数，$p$是一个质数，那么当$a$是$p$的倍数时，有：
$$a^p≡a(mod\ p)$$
当$a$不是$p$的倍数时，有：
$$a^{p-1}≡1(mod\ p)$$
对于本题，显然我们要用的是第二种情况，第二种情况又可以变形为：
$$a*a^{p-2}≡1(mod\ p)$$
上式恰好对应逆元的定义式，故$a$在$mod\ p$意义下的逆元为$a^{p-2}
那逆元不存在怎么办，不用担心，因为对应上面的式子$p-1$，有：
$$(p-1) \ mod \ 9901=0$$
即:
$$p \ mod \ 9901=1$$
所以该等比数列之和($mod\ p$意义下)为：
$$sum= 1+({p\ mod\ 9901})^1 +({p\ mod\ 9901})^2 +({p\ mod\ 9901})^3+ … + ({p\ mod\ 9901})^{n}$$
即：
$$sum=1+n$$
至此，本题就分析完了
#### 代码实现：
```cpp
#include<iostream>
#include<cstdio>
#define mod 9901
using namespace std;
int a,b,sa,n[10010][2],cot=0,ans=1;
int quick_pow(int ml,int nl)//快速幂
{
int s=1;
while(nl>0)
{
if(nl%2==1)
{
s=(s%mod)*(ml%mod)%mod;
}
ml=ml*ml%mod;
nl=nl>>1;
}
return s%mod;
}
int sum(int x,int y)
{
int k=0;
y=y*b;
if(x%mod==1)
{
k=(y+1)%mod;//当逆元不存在时
}
else
{
k=(quick_pow(x%mod,y+1)-1)%mod*quick_pow((x-1)%mod,mod-2)%mod;//当逆元存在时
}
return k%mod;
}
int main()
{
scanf("%d%d",&a,&b);
if(a==0)//特判，0的因数和就是0
{
printf("0\n");
return 0;
}
for(int i=2;i*i<=a;i++)//分解质因数
{
if(a%i==0)
{
cot++;
n[cot][0]=i;//记录质因数
n[cot][1]=1;//记录幂次
a=a/i;
while(a%i==0)
{
n[cot][1]++;//记录幂次
a=a/i;
}
}
}
if(a!=1)//可能a仍为因子
{
cot++;
n[cot][0]=a;
n[cot][1]=1;
}
for(int i=1;i<=cot;i++)
{
ans=ans*sum(n[i][0],n[i][1])%mod;
}
printf("%d\n",(ans%mod+mod)%mod);
return 0;
}
```
有用的话点个赞顶上去才能让更多人看到哦QAQ