约数之和
约数之和
假设现在有两个自然数 $A$ 和 $B$,$S$ 是 $A^B$ 的所有约数之和。
请你求出 $Smod9901$ 的值是多少。
输入格式
在一行中输入用空格隔开的两个整数 $A$ 和 $B$。
输出格式
输出一个整数,代表 $Smod9901$ 的值。
数据范围
$0≤A,B≤5\times 10^7$
输入样例:
1 |
|
输出样例:
1 |
|
解析
要求 $A^B$ 的所有约数和,先求 $A$ 的所有约数和,即对 $A$ 进行质因数分解,得到式子,$A = \prod ^n_{i = 1} p_i^{c_i}$,那么可以得到 $A^B = \prod ^n_{i = 1} p_i^{c_i\times B}$,即可以得到 $A^B$ 的约数之和,为:$\prod^n_{i = 1}(1 + p^1_i + p^2_i + ..+p^{c_i\times B}_i)$如果单纯的计算每个算式,这个复杂度就会与质因数的个数和 $B$ 的乘积有关,会超时。
再观察括号内的式子满足等比数列规律,但根据等比数列的求和公式,分母分子同时会含有公比 $q$ ,分子分母不能同时 $MOD$ 后作除法,所以无论是 $S = \frac{a_1-a_nq}{1-q}$ 还是 $S = \frac {a_1(1-q^n)}{1-q}$,都可能会被数据卡掉(前者的 $a_nq$ 和 后者的 $a_1q^n$,A、B一大就会卡掉)。
一条路走不通 再返回去看式子(这里假设式子中无B),
设 $n = 5$
就会有 $p^0 + p^1 + p^2 + p^3 + p^4 + p^5$ 总共 6 个数,我们将其拆分成相同个数的两份
$(p^0 + p^1 + p^2) + (p^3 + p^4 + p^5)$
然后再化简 $(p^0 + p^1 + p^2) + p^3(p^0 + p^1 + p^2)$
继续可得 $(p^0 + p^1 + p^2)\times(1 + p^3)$ ,这里是 $n$ 为奇数的情况
同理,当 $n$ 为偶数时(n = 4),可得最终式子$(p^0 + p^1) \times(1 + p^2) + p^4$
综上两种情况,再配合快速幂这样我们就把 $O(n)$ 时间复杂度的式子变成了 $O(log^2n)$,分开情况讨论就可以得到最终的答案。
看代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!