Poj1845 & 洛谷P1593 寄中寄

给定两个数 \(A\)，\(B\)，求 \(A^B\) 的因子和。

由唯一分解定理，\(A\) 可以表示成 \(p_1^{a_1}\times p_ 2^{a_2}\times p_3^{a_3}\times \cdots\times p_n^{a_n}\) 的形式。而 \(A^B\) 也就可以表示成 \(p_1^{a_1\times B}\times p_ 2^{a_2\times B}\times p_3^{a_3\times B}\times \cdots\times p_n^{a_n\times B}\)。题目中让我们求因子和，我们会因子和的公式！于是这道题的答案可以表示为 \(\left ( 1+p_1+p_1^{2}+\cdots+p_1^{a_1\times B} \right ) \times \left ( 1+p_2+p_2^{2}+\cdots+p_2^{a_2\times B} \right ) \times \cdots \left ( 1+p_n+p_n^{2}+\cdots+p_n^{a_n\times B} \right )\)，考虑用等差数列求和公式来进行计算。

首先令 \(s_1=1+p^{1}+p^{2}+\cdots+p^{n}\)

然后令 \(s_2=s_1\times p=p^{1}+p^{2}+\cdots+p^{n+1}\)

那么 \(s_2-s_1=s_1\times p-s_1=s_1\times (p-1)\)

这个式子又可以表示为 \(s_2-s_1=p^{n+1}-1\)

于是 \(s_1\times (p-1)=p^{n+1}-1\)

得出结论：\(s_1=\frac{p^{n+1}-1}{p-1}\)。

于是就可以快乐地计算了。因为有除法，所以考虑使用逆元。写代码的时候一定要搞清楚逆元的逻辑关系，很容易被绕晕。

Update On 2024/3/4：小技巧！循环的时候使用 i*i<=x 而不是 i<=sqrt(x)。后者在 poj 会CE，原因是 sqrt 的返回值是 double 类型，不强制转换会出问题。第二个小经验：逆元数组不要开太大。这题数组太大会RE。

Update On 2024/3/4：这道题两个坑。

• 取模的时候一定一定要先加取模数再取模，c++ 的取模机制会让负数取模变成负数。Hack：9901 0，输出应该是 \(1\) 而不是负数。

• 有些数是没有逆元的，所以一定要特判 i%9901==1。

贴个代码：

#include<iostream>
#include<cmath>
#define modd 9901
using namespace std;
long long Inv[500005];//5e6
long long ksm(int a,int b){
	if(b==0){
		return 1;
	}
	if(b%2==0){
		long long tmp=ksm(a,b/2)%modd;
		return (tmp*tmp)%modd;
	}
	else{
		return (a%modd*ksm(a,b-1)%modd)%modd;
	}
}
inline long long mod(int a,int b){
	return (a%b+b)%b;
}
inline long long inv(long long a,long long b){
	if(Inv[a]){
		return Inv[a];
	}
	Inv[a]=mod(-b/a*inv(b%a,b),b);
	return Inv[a];
}
bool Is_Prime(int x){
	if(x==2){
		return 1;
	}
	if(x==1){
		return 0;
	}
	for(int i=2;i<=sqrt((double)x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
inline long long get(long long &n,long long k){
	long long x=n,cnt=0;
	while(n%k==0){
		n/=k;
		cnt++;
	}
	return cnt;
}
long long a,b;
signed main(){
	cin>>a>>b;
	Inv[1]=1;
	long long ovovovovo=1;
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			long long _=get(a,i);
			if(i%9901==1){
				ovovovovo=ovovovovo*(_*b+1)%modd;
				ovovovovo%=modd;
				continue;
			}
			ovovovovo=ovovovovo*(ksm(i,b*_+1)-1);
			ovovovovo=mod(ovovovovo,modd);
			ovovovovo=ovovovovo*inv((i-1)%modd,modd);
			ovovovovo=mod(ovovovovo,modd);
		}
	}
	if(a>1){
		if(a%9901==1){
			ovovovovo=ovovovovo*(b+1)%modd;
			ovovovovo%=modd;
			cout<<ovovovovo<<endl;
			return 0;
		}
		ovovovovo=ovovovovo*(ksm(a,b+1)-1);
		ovovovovo=mod(ovovovovo,modd);
		ovovovovo=ovovovovo*inv((a-1)%modd,modd);
		ovovovovo=mod(ovovovovo,modd);
	}
	cout<<ovovovovo<<endl;
	return 0;
}

总结：gxyzoj 数据弱的一批。