Luogu P1593 因子和 题解

前言

题目传送门。

需要掌握以下前置知识：

• 唯一分解定理

• 约数和定理

• 等比数列求和

• 除法取模

• 费马小定理或扩展欧几里德算法求逆元

题意：

求 \(a^b\) 的约数和。答案对 \(9901\) 取模。\(a,b\le 5\times 10^7\) 。

思路

首先，我们不妨先对 \(a\) 分解质因数。

\[a=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n} \]

则 \(a^b\) 可分解如下：

\[a^b=p_1^{a_1b}p_2^{a_2b}\cdots p_n^{a_nb} \]

那么其约数和可以这样计算：

\[sd = (p_1^0+p_1^1+\cdots+p_1^{a_1b})(p_2^0+p_2^1+\cdots+p_2^{a_2b})\cdots (p_n^0+p_n^1+\cdots+p_n^{a_nb}) \]

注意到这个式子中的每一个括号内都是一个等比数列。我们拿出等比数列求和公式：

\[S_n=\sum_{i=1}^n a_i = \frac{a_1(1-q^n)}{1-q},\ q\neq 1 \]

注意，上式中各字母的含义是针对等比数列的，与思路分析时不同。我们不难得出其中公比 \(q=p_i\) ，项数 \(n=a_ib+1\) ，首项 \(a_1=1\) 。这样，我们代入公式，就可以求得约数和里每个括号的结果，累乘即可得到最终答案。

需要注意的是，我们还需要答案对 \(9901\) 取模，而公式中的除法取模需要用到逆元。本题中 \(9901\) 是一个质数，所以我们可以直接用费马小定理求逆元，更方便。费马小定理告诉我们，若 \(n\) 是质数且有 \(\gcd(a, n)=1\) ，则

\[a^{n-1} \equiv 1\ (\ \bmod\ n\ ) \]

于是我们可推出

\[a\cdot a^{n-2} \equiv 1\ (\ \bmod\ n\ ) \]

从而 \(a^{n-2}\) 就是 \(a\) 在 \(\bmod\ n\) 意义下的逆元，记作 \(a^{-1}\) 。从而我们就可以把除法取模转化为乘法取模：

\[(a\div b)\bmod n = (a\times b^{-1})\bmod n \]

（同上，这里的 \(a,b,n\) 的意义也与思路分析时的不同。）

于是，这道题就基本解决了。

不过用这种思路做题，大概率会遇到如下坑点。在此稍作提醒。

1. 记得特判 \(a=0\) 的情况。

2. 当 \(p_i\bmod 9901 = 1\) 时，分母 \(1-q,\ q=p_i\) 的逆元在 \(\bmod\ 9901\) 意义下不存在。此时除法取模会错。正确的做法是特判此种情况，并且，此情况下这个括号内的等比数列求和结果时 \(a_ib+1\) 。原理请自己思考。

   可以参考如下 hack 数据：

   input:
   217823 1
   output:
   2
   

代码

#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inv(x) qpow((x), MOD-2)
#define int long long
#define MIKU 0
using namespace std;

const int N = 5e7, MOD = 9901;

int a, b, ans = 1;
int lis[4000005], pw[4000005];
void fac(int n) {
	for(int i=2; i*i<=n; i++) {
		if(n % i == 0) {
			lis[++lis[0]] = i;
			while(n % i == 0) n /= i, pw[lis[0]] ++;
		}
	}
	if(n > 1) lis[++lis[0]] = n, pw[lis[0]]++;
}

int qpow(int a, int n) {
	int ans = 1;
	a %= MOD;
	while(n > 0) {
		if(n & 1) ans = (ans * a) % MOD;
		a = (a * a) % MOD;
		n >>= 1;
	}
	return ans;
}

bool check(int a) {
	for(int i=2; i*i<=a; i++) {
		if(a % i == 0) return 0;
	}
	return 1;
}

signed main() {
	fastio;
	cin>>a>>b;
	if(a == 0) {
		cout<<0;
		return 0;
	}
	fac(a);
	for(int i=1; i<=lis[0]; i++) {
		int t1 = (1 - qpow(lis[i], pw[i] * b + 1)) % MOD;
		int t2 = (1 - (lis[i] % MOD)) % MOD;
		int t = (t1 * inv(t2)) % MOD;
		if(lis[i] % MOD == 1) t = pw[i] * b + 1;
		ans = (ans * t) % MOD;
	}
	cout<<ans;
	return MIKU;
}