洛谷题解 P1593 【因子和】

题意简述:

求$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)$$

$x$即为$a$的逆元,反之成立

注意此处的$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}$

$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$$

至此,本题就分析完了

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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;
}

题目详见:https://www.luogu.com.cn/problem/P1593