题面
思路
显然要对A分解质因数，可得
A
B
A^B
AB的所有约数之和(求模)为:
S
u
m
=
(
1
+
p
1
+
p
1
2
+
…
+
p
1
B
∗
c
1
)
∗
(
1
+
p
2
+
p
2
2
+
…
+
p
2
B
∗
c
2
)
∗
⋯
∗
(
1
+
p
n
+
p
n
2
+
…
+
p
n
B
∗
c
n
)
m
o
d
9901
(1)
Sum = (1+p_1+p_1^2+\ldots+p_1^{B*c_1})*(1+p_2+p_2^2+\ldots+p_2^{B*c_2})*\cdots* \\ (1+p_n+p_n^2+\ldots+p_n^{B*c_n}) \space mod\space9901 \tag{1}
Sum=(1+p1+p12+…+p1B∗c1)∗(1+p2+p22+…+p2B∗c2)∗⋯∗(1+pn+pn2+…+pnB∗cn) mod 9901(1)
那么显然要算积中的每一项(求模)，由等比求和公式可得
(
1
+
p
i
+
p
i
2
+
…
+
p
i
B
∗
c
i
)
m
o
d
9901
=
p
i
B
∗
c
i
+
1
−
1
p
i
−
1
m
o
d
9901
(2)
(1+p_i+p_i^2+\ldots+p_i^{B*c_i})\space mod\space9901 = \frac{p_i^{B*c_i+1}-1}{p_i-1} \space mod\space9901 \tag{2}
(1+pi+pi2+…+piB∗ci) mod 9901=pi−1piB∗ci+1−1 mod 9901(2)
显然9901是个质数，只要
(
p
i
−
1
)
(p_i-1)
(pi−1)不是9901的倍数，两者就互质，可以用乘法逆元计算，先用快速幂计算分子
(
p
B
∗
c
1
+
1
−
1
)
m
o
d
9901
(p^{B*c_1+1}-1)\space mod\space 9901
(pB∗c1+1−1) mod 9901，然后根据费马小定理的推论，乘法逆元即为
(
p
i
−
1
)
9899
m
o
d
9901
(p_i-1)^{9899}\space mod\space 9901
(pi−1)9899 mod 9901,也用快速幂计算即可
那么如果
(
p
i
−
1
)
(p_i-1)
(pi−1)是9901的倍数怎么办，显然有
p
i
≡
1
(
m
o
d
9901
)
(3)
p_i\equiv1(mod\space 9901) \tag{3}
pi≡1(mod 9901)(3)那么就有
(
1
+
p
i
+
p
i
2
+
…
+
p
i
B
∗
c
i
)
≡
(
1
+
1
2
+
1
3
+
…
+
1
B
∗
c
i
)
≡
B
∗
c
i
+
1
(
m
o
d
9901
)
(4)
(1+p_i+p_i^2+\ldots+p_i^{B*c_i})\equiv(1+1^2+1^3+\ldots+1^{B*c_i})\equiv B*c_i+1(mod\space 9901) \tag{4}
(1+pi+pi2+…+piB∗ci)≡(1+12+13+…+1B∗ci)≡B∗ci+1(mod 9901)(4)
所以两种情况分开算就行了
注意事项
1)以下代码中没有一处的long long是没用的，做大数题(基本1e5就要开始注意乘法，时刻注意乘方)一定要时刻注意int的溢出问题(上限也就2e9多一点)，每一个数学运算符都要对两侧数字的范围进行判断，然后判断结果会不会溢出(这里mod还比较小，可以用int，再大一点的mod就最好全部用long long了)
注意运算符优先级，先说一下我的理解(这里我也不确定是不是这样的)：比如a = (long long)a*b%c，由于()的运算符最高，先将a转化为long long，然后乘以b，最后再模上c(*和%的运算优先级相同，右结合，所以直接从左向右算就行了)，最后因为a是int，赋值时又强制类型转换为int，再赋值给a
下面对所有的long long处进行解释：
ans = (ll)ans*a % mod;\\(1)
(1)对于强制类型转换的两个变量：
a
n
s
∈
[
0
,
9901
]
,
a
∈
[
0
,
5
∗
1
0
7
]
(1)
ans \in[0,9901],\space a\in[0,5*10^7] \tag{1}
ans∈[0,9901], a∈[0,5∗107](1)
注意以上的a只有第一次是这个范围，之后会在[1,9901]之间，但是因为第一次，还得用long long，下面遇到相同的情况同理
a = (ll)a*a % mod;\\(2)
int qpow(int a,ll b)\\(3)
(3)注意主函数调用qpow的时候，如果是分母(乘法逆元算)就没有问题(9989次)，但是如果是分子，都是b*c[i]作指数，为了达到c[i]的最大情况，这里我们不妨假设只有2作因子，那么指数最大可以达到
⌊
l
o
g
2
(
5
∗
1
0
7
)
⌋
=
25
(3)
\lfloor log_2(5*10^{7})\rfloor = 25 \tag{3}
⌊log2(5∗107)⌋=25(3)
那么就有
b
∈
[
0
,
5
∗
1
0
7
]
c
[
i
]
∈
[
0
,
25
]
b
∗
c
[
i
]
∈
[
0
,
1.25
∗
1
0
9
]
(3)
b\in[0,5*10^7] \space c[i]\in[0,25]\space b*c[i]\in[0,1.25*10^9] \tag{3}
b∈[0,5∗107] c[i]∈[0,25] b∗c[i]∈[0,1.25∗109](3)
这里做题时因为没有办法做太精确的运算，当时估计是c[i]大概是个两位数，这就很有可能溢出2e9的多一点的int上限，而且如读者所见，只要这个两位数再多大概十几，就溢出了，因此用long long 是合理的
下面同理，不多说了
(4)
ans= ((ll)b*c[i]+1) % mod *ans % mod;\\(4)
2)对于取余数类的问题，最好不要使用*= +=这类符号，有可能会因为没给赋值的变量取模而出问题(不要省写)
3)对一个数分解质因数时(经验)，最多开20个数就够了，前10个质数的乘积就已经基本大于int上限了，如果有更大的质数，肯定有这前十个质数没有的情况，而且大质数在范围内肯定质数更少
反思
1)质因数分解，快速幂不熟
2)对取余类问题不要省写
3)遇到int上限问题，每打一个算式都要想清楚有没有可能溢出，或者有可能越界直接用long long(不就两倍空间嘛)
4)乘法逆元还要再熟悉
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int num =0;
const int mod = 9901;
int p[20],c[20];
void divide(int n)
{
memset(c,0,sizeof(c));
for(int i = 2; i*i<=n;i++)
{
if(n%i == 0)
{
p[++num] = i;//add first cause loop next
while(n % i == 0) n/=i,c[num]++;
}
}
if(n > 1) p[++num] = n,c[num] = 1;//if n is prime,no segment divide it
}
//Caution
int qpow(int a,ll b)
{
int ans = 1;
for(;b;b>>=1)
{
if(b & 1)
ans = (ll)ans*a % mod;
a = (ll)a*a % mod;
}
return ans;
}
int main()
{
int a,b;
cin >> a >> b;
divide(a);
int ans = 1;
for(int i = 1;i<=num;i++)
{
if((p[i]-1)%mod ==0)
{
ans= ((ll)b*c[i]+1) % mod *ans % mod;
}
else
{
int tmp = (qpow(p[i],(ll)b*c[i]+1)-1+mod)%mod;
int tmp2 = qpow(p[i]-1,mod-2);
ans = ans*tmp% mod*tmp2%mod;
}
}
cout << ans <<endl;
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容