97. 约数之和(分治)

求 a b a^b ab的约数和 模 p p p的值。

σ ( a b ) ( m o d p ) \large \sigma(a^b)\pmod{p} σ(ab)(modp)

首先利用算数基本定理：

a b = ( p 1 k 1 p 2 k 2 … p m k m ) b = p 1 k 1 b p 2 k 2 b … p m k m b \large a^b=(p_1^{k_1}p_2^{k_2}\dots p_m^{k_m})^b=p_1^{k_1b}p_2^{k_2b}\dots p_m^{k_mb} ab=(p1k1​​p2k2​​…pmkm​​)b=p1k1​b​p2k2​b​…pmkm​b​

又 σ ( n ) = ( 1 + p 1 + p 1 2 ⋯ + p 1 k 1 ) ( 1 + p 2 + p 2 2 ⋯ + p 2 k 2 ) … ( 1 + p m + p m 2 + ⋯ + p m k m ) = σ ( p 1 k 1 ) σ ( p 2 k 2 ) … σ ( p m k m ) \sigma(n)=(1+p_1+p_1^2\dots+p_1^{k_1})(1+p_2+p_2^2\dots+p_2^{k_2})\dots (1+p_m+p_m^2+\dots+ p_m^{k_m})=\sigma(p_1^{k_1})\sigma(p_2^{k_2})\dots \sigma(p_m^{k_m}) σ(n)=(1+p1​+p12​⋯+p1k1​​)(1+p2​+p22​⋯+p2k2​​)…(1+pm​+pm2​+⋯+pmkm​​)=σ(p1k1​​)σ(p2k2​​)…σ(pmkm​​)

所以我们只需要求出 σ ( p i k i b ) \large \sigma(p_i^{k_ib}) σ(piki​b​)即可。

这个是一个等比数列，有两种方法求解：

1.分治法。

2.公式法。

分治法：令 σ ( p k − 1 ) = f ( p , k ) = p 0 + p 1 + ⋯ + p k − 1 \sigma(p^{k-1})=f(p,k)=p^0+p^1+\dots+p^{k-1} σ(pk−1)=f(p,k)=p0+p1+⋯+pk−1

当 k k k为偶数时：
f ( p , k ) = （ p 0 + p 1 + ⋯ + p k 2 − 1 ) + ( p k 2 + ⋯ + p k − 1 ) = p k 2 ( 1 + f ( a , k 2 ) ) f(p,k)=（p_0+p_1+\dots+p^{\small\dfrac{k}{2}-1})+(p^{\small\dfrac{k}{2}}+\dots+p_{k-1})=p^{\small\dfrac{k}{2}}(1+f(a,\dfrac{k}{2})) f(p,k)=（p0​+p1​+⋯+p2k​−1)+(p2k​+⋯+pk−1​)=p2k​(1+f(a,2k​))

当 k k k为奇数时，拆掉最后面一项变为偶数情况即可。

代码

// Problem: 约数之和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/99/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2021-07-02 00:16:08
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=9901;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
vector<PII>v;
void init(int n){
	for(int i=2;i*i<=n;i++)
		if(n%i==0){
			PII x;
			x.fi=i,x.se=0;
			while(n%i==0) x.se++,n/=i;
			v.pb(x);
		}
	if(n>1) v.pb(n,1);
}
ll ksm(ll a,ll n,ll m=mod){
	ll ans=1;
	while(n){
		if(n&1) ans=ans*a%m;
		a=a*a%m;
		n>>=1;
	}
	return ans;
}
ll f(ll a,ll k){
	if(k==1) return 1;
	if(k%2==0) return (ksm(a,k/2)+1)*f(a,k/2)%mod;
	return (f(a,k-1)+ksm(a,k-1))%mod;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	init(a);
	ll ans=1;
	for(auto x:v){
		int u=x.fi,v=x.se*b;
		ans=ans*f(u,v+1)%mod;
	}
	if(!a) ans=0;
	printf("%lld\n",ans);
	return 0;
}

---

公式法：利用等比数列求和公式即可。

σ ( p k − 1 ) = f ( p , k ) = p k − 1 p − 1 \sigma(p^{k-1})=f(p,k)=\dfrac{p^{k}-1}{p-1} σ(pk−1)=f(p,k)=p−1pk−1​

这里用快速幂+逆元即可。

注意当 ( p − 1 ) ( m o d m o d ) = 0 (p-1)\pmod {mod}=0 (p−1)(modmod)=0时，答案即为 k k k，因为 p ( m o d m o d ) = 1 p\pmod{mod}=1 p(modmod)=1。