原理
约数个数定理
对一个大于1的整数$n$，$n$可以分解质因数为$\prod_{i=1}^{k}p_i^{a_i} = {p_1}^{a_1}·{p_2}^{a_2}···{p_k}^{a_k}$
则n的正约数的个数就是$f(n) = \prod_{i=1}^{k}a_i+1=(a_1+1)(a_2+1)···(a_k+1)$，这个很好证明，因为$p_1^{a_1}$的约数有$p_1^0,p_1^1,p_1^2…p_1^{a1}$，共$(a_1+1)$个，同理$p_k^{a_k}$的约数有$(a_k+1)$个
约数定理
$n$的$(a_1+1)(a_2+1)···(a_k+1)$个正约数的和为：
$$
(p_1^0+p_1^1+…+p_1^{a_1})(p_2^0+p_2^1+…p_2^{a_2})…(p_k^0+p_k^1+…p_k^{a_k})
$$
举个例子，$180 = 2^2*3^2*5^1$
约数个数：$(2+1)(2+1)(1+1) = 18$
约数和：$(1+2+4)(1+3+9)(1+5) = 546$
定义sum(n,k)为$p^0+p^1+…+p^k$，分成两部分的和变为$(p^0+…+p^{\frac{k}{2}})+(p^{\frac{k}{2}+1}+…p^k)$
后面的多项式提取$p^{\frac{k}{2}+1}$，变成$(p^0+…+p^{\frac{k}{2}})+p^{\frac{k}{2}+1} * (p^0+…p^{\frac{k}{2}})$
将两项合并$(1+p^{\frac{k}{2}+1}) * (p^0+…+p^{\frac{k}{2}})$，这个式子可以转化为$(1+p^{\frac{k}{2}}) * sum(p, \frac{k}{2})$
代码
#include <iostream>
#include <cmath>
using namespace std;
const int M = 9901;
int qmi(int a, int b)
{
a %= M;
int res = 1; //乘积初始化为1
while (b)
{
if (b&1) res = res * a % M;
a = a * a % M;
b >>= 1; //右移>>
}
return res;
}
int sum(int p, int k)
{
if (k == 0) return 1;
if (k & 1) return sum(p, k / 2) % M * (1 + qmi(p % M, k / 2 + 1) % M) % M; //中间变量取模，防止溢出
else return (sum(p % M, k - 1) % M * p % M + 1) % M;
}
int main()
{
int a;
cin >> a;
int res = 1; //累积初始化为1
for (int i = 2; i <= a; i++)
{
int s = 0;
while (a % i == 0)
{
s ++ ;
a /= i;
}
if (s) res = res % M * sum(i, s) % M;
}
if (!a) res = 0;
cout << res << endl;
}