前言
题目传送门。
需要掌握以下前置知识：
-
唯一分解定理
-
约数和定理
-
等比数列求和
-
除法取模
-
费马小定理或扩展欧几里德算法求逆元
题意：
求 \(a^b\) 的约数和。答案对 \(9901\) 取模。\(a,b\le 5\times 10^7\) 。
思路
首先，我们不妨先对 \(a\) 分解质因数。
则 \(a^b\) 可分解如下：
那么其约数和可以这样计算：
注意到这个式子中的每一个括号内都是一个等比数列。我们拿出等比数列求和公式：
注意，上式中各字母的含义是针对等比数列的，与思路分析时不同。我们不难得出其中公比 \(q=p_i\) ，项数 \(n=a_ib+1\) ，首项 \(a_1=1\) 。这样，我们代入公式，就可以求得约数和里每个括号的结果，累乘即可得到最终答案。
需要注意的是，我们还需要答案对 \(9901\) 取模，而公式中的除法取模需要用到逆元。本题中 \(9901\) 是一个质数，所以我们可以直接用费马小定理求逆元，更方便。费马小定理告诉我们，若 \(n\) 是质数且有 \(\gcd(a, n)=1\) ，则
于是我们可推出
从而 \(a^{n-2}\) 就是 \(a\) 在 \(\bmod\ n\) 意义下的逆元，记作 \(a^{-1}\) 。从而我们就可以把除法取模转化为乘法取模：
（同上，这里的 \(a,b,n\) 的意义也与思路分析时的不同。）
于是，这道题就基本解决了。
不过用这种思路做题，大概率会遇到如下坑点。在此稍作提醒。
-
记得特判 \(a=0\) 的情况。
-
当 \(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;
}