约数之和
题目描述
假设现在有两个自然数A和B,S是$A^B$的所有约数之和。
请你求出S mod 9901的值是多少。
输入格式
在一行中输入用空格隔开的两个整数A和B。
输出格式
输出一个整数,代表S mod 9901的值。
数据范围
$0≤A,B≤5×10^7$
输入样例:
1 | 2 3 |
输出样例:
1 | 15 |
注意: A和B不会同时为0。
题解
考虑将$A$进行质因数分解.
$A = \prod_{i = 1} ^ {n} p_i ^ {a_i} = p_1 ^ {a_1} p_2 ^ {a_2} p_3 ^ {a_3} … p_n ^ {a_n}$
那么
$A^B = \prod_{i = 1} ^ {n} p_i ^ {a_i B} = p_1 ^ {a_1 B} p_2 ^ {a_2 B} p_3 ^ {a_3 B} … p_n ^ {a_n * B}$
$S$定义为$A^B$的约数和,那么
$S = \prod_{i = 1}^n \sum_{j=0}^{a_i*B} p_i^j $
$S= (p_1^0+p_1^1+…+p_1^{a_1B})(p_2^0+p_2^1+…+p_2^{a_2B})…(p_n^0+p_n^1+…+p_n^{a_nB})$
式子看似复杂,简单的讲就是相当于在式子中的每一个因子项。也就是每一个括号里面取一个。然后取得$n$相乘起来就得到了一个$A^B$的约数。
现在我们的问题就是求:$\sum_{j=0}^{a_i*B}p_i^j$
容易看出。这是一个等比数列前n项和。省赛就做过一个这个玩意儿。当时想复杂了。想成用等比数列前$n$项和公式,但是当时它那个题目的模数是输入,也就是模数可能是合数。这题中模数确定是9901。是一个素数。可以考虑使用等比数列求和公式。当然,可以使用分治,
1 |
|