约数之和

题意：

求出$a^b$的约数之和。

思路：

将a分解质因数得$a=p_1^{num1}\ast p_2^{num2}\ast ......p_n^{numn}$，那么$a^b$分解质因数就是$a=p_1^{num1+b}\ast p_2^{num2+b}\ast ......p_n^{numn+b}$，于是：约数之和就为$sum=(1+p_1+p_1^2+...+p_1^{num1+b})\ast (1+p_2+p_2^2+...+p_2^{num2+b})\ast ...\ast (1+p_n+p_n^2+...+p_n^{numn+b})$。
上面这个式子由乘法分配定理得到，可以很轻易的想到，要得到所有的约数，只需要让不同的质因数的不同次方相乘即可。
然后发现这个式子括号里的每一项都是等比数列，所以只需要用等比数列求和公式：$s=a_1\ast (1-q^n)/(1-q)$，用到这里要稍微转换一下：$s=a_1\ast (q^n-1)/(q-1)$然后用快速幂逆元取模即可，要注意，当分子取模为0时，逆元是不存在的，但既然分子取模为0，即$a_1\ast (q^n-1)$%$mod=0$，因为这里$a_1$为1，所以$（q^n-1）$%$mod=0$，所以$q^n$%$mod=1$，此时这个等比数列的值$s=项数$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 9901;

int cnt;
int pri[1000010];
int vis[1000010];
int ans[1000010];
int num[1000010];
ll qpow(ll a,ll b)
{
	ll res = 1;
	while(b)
	{
		if(b%2)res = res*a%mod;
		b = b>>1;
		a = a*a%mod;
	}
	return res;
}
void oula()
{
	for(int i = 2; i <= 1000000; i++)
	{
		if(!vis[i])pri[++cnt] = i;
		for(int j = 1; j <= cnt && pri[j]*i <= 1000000; j++)
		{
			vis[i*pri[j]] = 1;
		}
	}
}
int main()
{
	__int128 p;
	oula();
	ll a,b;
	cin>>a>>b;
	if(a == 0)
	{
		cout<<0<<endl;
		return 0;
	}
	int c = 0,now = a;
	for(int i = 1; i <= cnt; i++)
	{
		now = a;
		if(pri[i] > now)break;
		if(now%pri[i] == 0)ans[++c] = pri[i];
		while(now%pri[i]==0)
		num[c]++,now/=pri[i];
	}
	ll res = 1;
	for(int i = 1; i <= c; i++)
	{
		if((qpow(ans[i],b*num[i]+1)+mod-1)%mod != 0)
		res *= (qpow(ans[i],b*num[i]+1)+mod-1)%mod*qpow(ans[i]-1,mod-2)%mod;
		else res*=(num[i]*b+1)%mod; 
		res%=mod;
	}
	cout<<(res)%mod<<endl;
}

最后

以上就是失眠煎蛋为你收集整理的约数之和。题意：思路：的全部内容，希望文章能够帮你解决约数之和。题意：思路：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。