自动搬运

查看原文

来自洛谷，原作者为

	C_Cong 1+1=⑨ ⑨⑨=⑥ ⑥/⑥=1 雾の湖城管*

搬运于2025-08-24 21:26:52，当前版本为作者最后更新于2020-05-06 13:33:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

博客传送门

题意简述：

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

至此，本题就分析完了

代码实现：

#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