#數論，等比數列，乘法逆元#poj 1845 Sumdiv

題目

求 A B A^B AB的約數和 m o d    9901 \mod9901 mod9901

分析

首先A的約數和是

## ∏ i = 1 m ∑ j = 0 c i p i j \prod_{i=1}^m\sum_{j=0}^{c_i}{p_i}^j ∏i=1m​∑j=0ci​​pi​j

那麼 A B A^B AB的約數和為

## ∏ i = 1 m ∑ j = 0 c i p i j ∗ B \prod_{i=1}^m\sum_{j=0}^{c_i}{p_i}^{j*B} ∏i=1m​∑j=0ci​​pi​j∗B

那麼對于單個的質因數應該怎麼做，首先它轉換成

## 1 + p 1 + p 2 + p 3 + . . . + p B ∗ c 1+p^1+p^2+p^3+...+p^{B*c} 1+p1+p2+p3+...+pB∗c

根據等比數列公式可得答案為

## ( p B ∗ c − 1 ) / ( p − 1 ) (p^{B*c}-1)/(p-1) (pB∗c−1)/(p−1)

問題是 m o d mod mod無法在除法下進行，是以要用乘法逆元，特别地，當 p − 1 p-1 p−1是9901的倍數時，那麼答案為 B ∗ c + 1 B*c+1 B∗c+1

代碼

#include <cstdio>
using namespace std;
typedef long long ll;
ll a,b,ans=1;
ll ksm(ll x,ll y){//快速幂
	ll ans=1;
	while (y){
		if (y&1) ans=ans*x%9901;
		x=x*x%9901; y>>=1;
	}
	return ans;
}
ll answer(ll x,ll y){
	if ((x-1)%9901==0) return (y+1)%9901;//特判
	int a=ksm(x,y+1); a=(a+9900)%9901;//分子在0到9900之間
	int b=ksm(x-1,9899); return a*b%9901;//乘法逆元
}
int main(){
	scanf("%lld%lld",&a,&b);
	for (ll i=2;i*i<=a;i++)
	if (a%i==0){//質因數分解
		ll sum=0;
		while (a%i==0) sum++,a/=i;
		ans=ans*answer(i,sum*b)%9901;
	}
	if (a>1) ans=ans*answer(a,b)%9901;//特判
	printf("%lld",ans);
	return 0;
}