【题目来源】
洛谷：P1593 因子和 - 洛谷
【题目描述】
输入两个整数 \(a\) 和 \(b\)，求 \(a^b\) 的因子和。
由于结果太大，只要输出它对 \(9901\) 取模的结果。
【输入】
仅一行，为两个整数 \(a\) 和 \(b\)。
【输出】
输出一行一个整数表示答案对 \(9901\) 取模的结果。
【输入样例】
2 3
【输出样例】
15
【算法标签】
《洛谷 P1593 因子和》 #数学#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型
const int mod = 9901; // 模数int a, b; // 输入的两个数
int p[10005]; // 存储质因数的数组
int cnt[10005]; // 存储对应质因数的指数
int len; // 不同质因数的个数
int inv[10005]; // 存储逆元的数组
int ans = 1; // 最终结果/*** 质因数分解函数* @param x 要分解的数*/
void init_1(int x)
{// 分解质因数for (int i = 2; i * i <= x; i++){if (x % i == 0) // 找到质因数{len++;p[len] = i;// 计算该质因数的指数while (x % i == 0){cnt[len]++;x /= i;}}}// 处理最后一个质因数if (x != 1){len++;p[len] = x;cnt[len] = 1;}
}/*** 快速幂函数* @param a 底数* @param b 指数* @param p 模数* @return a^b mod p*/
int qmi(int a, int b, int p)
{int mul = 1;while (b){if (b & 1) // 如果当前位为1{mul = mul * a % p;}a = a * a % p;b >>= 1; // 右移一位}return mul;
}/*** 初始化逆元数组*/
void init_2()
{for (int i = 1; i <= len; i++){// 计算(p[i]-1)的逆元inv[i] = qmi(p[i] - 1, mod - 2, mod);}
}/*** 计算单个质因数对应的等比数列和* @param x 质因数的索引* @return 等比数列和 mod 9901*/
int calc(int x)
{// 特殊情况：p[x]-1是mod的倍数if ((p[x] - 1) % mod == 0){return 1 + cnt[x] * b;}int q = p[x]; // 公比int k = b * cnt[x] + 1; // 项数// 计算等比数列和：S = (q^k - 1) / (q - 1)int res = qmi(q, k, mod); // q^k mod modres = (res - 1 + mod) % mod; // q^k - 1 mod modres *= inv[x]; // 乘以逆元，相当于除以(q-1)res %= mod;return res;
}signed main() // 使用signed代替int（因为定义了#define int long long）
{cin >> a >> b;// 特殊情况处理if (a == 1 || b == 0){cout << 1 << endl;return 0;}// 第一步：对a进行质因数分解init_1(a);// 第二步：初始化逆元数组init_2();// 第三步：计算每个质因数对应的等比数列和，并累乘for (int i = 1; i <= len; i++){ans *= calc(i);ans %= mod; // 每一步都要取模}cout << ans << endl;return 0;
}
【运行结果】
2 3
15