前导知识：
1、算术基本定理（唯一分解定理）
(a={p_1}^{k_1} * {p_2}^{k_2}... * {p_m}^{k_m})
2、快速幂
3、约数和公式
(sigma(a)=prodlimits_{i=1}^{k}(1+p_{i}+p_{i}^{2}+cdots+p_{i}^{r_{i}}))
4、逆元概念及求法
5、矩阵快速幂
TODO
解法1【多项式展开+逆元】
既然要求约数和，那先分解质因数。根据唯一分解定理:
因为本题要分解的是(a^b)，上式写成：
要求的是约数和，套用约数和公式：
依题意，本题:
(ans=(1+p_1 + {p_1}^2 + {p_1}^3 +...+{p_1}^{k_1+b}) * (1+p_2 + {p_2}^2 + {p_2}^3 +...+{p_2}^{k_2+b}) *... * (1+p_n + {p_n}^2 + {p_n}^3 +...+{p_n}^{k_n+b}))
根据在约数和公式那篇文章总结的经验，我们知道，是可以采用等比数列求和公式进行计算约数和的：
多个连乘积就是：
这个又是(k_i+b+1)次方，又是连乘积，结果很快就会非常大，计算机会装不下的，还好题目告诉可以取模，(MOD=9901)。看清楚啊，这个(9901)是个质数啊！这非常重要啊！它要不是质数，不能用后面的费马小定理啊，那就要用扩展欧几里德了
现在整理一下思路：
（1）那个大乘方怎么取模呢？我们不能真的暴力算出(p_i^{k_i+b+1})啊，其实我们想算的是(p_i^{k_i+b+1} mod 9901)啊！
答：快速幂又能快速算出(N)次方，又能在算的过程中取模，(Match!)
(2)分数(frac{p_i^{k_i+b+1}-1}{p_i-1})怎么取模呢？
答: 这样分两种情况分别讨论：
2.1 分母(p_i-1)不是(MOD)的倍数，即(p_i-1)与(MOD)互质：
如果分数求模要使用逆元。通过逆元将除(p-1)转化为乘(p−1)的逆元即可。
2.2 分母(p_i-1)是(MOD)的倍数
这时逆元是不存在的，也不要求啦！求也是没有~~哪咋办啊，5555~
这么复杂？？一个个来吧，
办法如下：
先看存在逆元的，就是((p-1)\%MOD!=0)
在前导知识中讲过，求逆元有两种办法，分别适用于
(MOD)是质数,并且(p-1)不是(MOD)的整数倍--- >费马小定理+快速幂 本题可以使用这个！
(p)是质数的话，并且(b)不是(p)的整数倍，那么(b^{p−2})就是(b)在模(p)下的逆元。
(MOD) 可以是质数，也可以不是质数,但(p-1)不是(MOD)的整数倍--->扩展欧几理德算法 [这个方法似乎更万能啊，但一般MOD都是质数，所以费马小定理就应该OK]
如果不满足 "(p-1)不是(MOD)的整数倍" 这个条件，就不存在逆元。
那逆元不存在怎么办,就是((p-1)\%MOD=0) 也就是 (p-1)是(MOD)的整数倍时：
不用担心，因为对应上面的式子(p-1)，有：
所以(ans=1+(p mod 9001)^1 + (p mod 9001)^2 +(p mod 9001)^3+...+(p mod 9001)^n)
即：
至此，本题就分析完了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10010; //质数因子个数上限，因为a的数据范围是5*10^7,开根号就是10^4肯定能装得下了
const int MOD = 9901; //要模的质数
int primes[N]; //质数因子数组
int idx; //质数因子数组下标游标
LL res = 1; //结果,因为是要乘来乘去，初始值需要给1
int a, b; //a的b次方
unordered_map<int, int> mc; //mc对应着幂次 key：质数 value:个数
// 快速幂模板[与yxc的有一点点区别，把p=MOD写在代码里了，减少了参数传入]
int qmi(int a, int k) {
int res = 1; //答案
while (k) { //一路让k变小直到为0停止
if (k & 1) res = (LL) res * a % MOD; //如果k的个位是1的话
k >>= 1; //右移一位
a = (LL) a * a % MOD; //1-2-4-8-16，就是每进一位，是把a=a*a,注意使用long long 防止在乘积过程中爆了int
}
return res;
}
//约数和公式的一部分，等比数列求和公式
// res=(p^(k+1)-1)/(p-1)
// 这里k还要乘一个b
int solve(int p, int k) {
int res;
k *= b; //每一个质因子的幂次都还要乘以原题中的指数的大小
if ((p - 1) % MOD == 0) res = (k + 1) % MOD; //当a,p不互质时，逆元不存在 (p-1)%MOD=0,则p%MOD=1,
// 此时，就可以直接计算原始公式 res=1+(p mod 9901)^1+(p mod 9901)^2+(p mod 9901)^3+...+(p mod 9901)^k
// 而不是面对等比数列求和公式那个带分母的式子，因为我们无法处理除法取模，这时逆元不存在！
// res=k+1
else {
//MOD肯定是质数，而且 (p-1)%MOD!=0,符合费马小定理，在这里就是 (p-1)^(MOD-2)
int inv = qmi((p - 1) % MOD, MOD - 2); //费马小定理求出逆元
//利用等比数列求和公式
res = (qmi(p % MOD, k + 1) - 1) % MOD * inv % MOD;
}
return res;
}
int main() {
//读入a和b,准备计算a^b
scanf("%d%d", &a, &b);
/***下面的代码在分解质数因子*************************************************************/
//a分解质因子，求其幂次
for (int i = 2; i * i <= a; i++) {
//如果发现a的一个因子i
if (a % i == 0) {
primes[++idx] = i; //质因子数组维护
mc[idx] = 1; //指数幂次数+1
a /= i; //去掉这个因子
while (a % i == 0) { //除干净它
mc[idx]++; //指数幂次数+1
a /= i; //继续缩小
}
}
}
//可能剩余一个很大的质因子数
if (a > 1) {
primes[++idx] = a;
mc[idx] = 1;
}
/***上面的代码在分解质数因子*************************************************************/
//连乘,遍历所有质数因子
for (int i = 1; i <= idx; i++) res = res * solve(primes[i], mc[i]) % MOD;
//输出
printf("%d
", (res % MOD + MOD) % MOD);//怀疑测试数据14中有负数，所以这样写才能通过！
return 0;
}