冒泡ioa
冒泡ioa

[poj1845]Sumdiv

题目

题目描述

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

输入

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

输出

The only line of the output will contain S modulo 9901.

样例输入

样例输出

提示

\( 2^3 = 8. \)
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).

来源

Romania OI 2002

传送门

Sumdiv

题解

问题分析

刚一看到这个题,一股浓浓的数论感就扑面而来,求A^B的约数和,暴力当然是不可取的,我们不妨换个角度
如果我们把A分解质因数,表示为

A=p_1^(c_1)_p_2^(c_2)_p_3^(c_3)_..._p_n^(c_n)

那么\( A^B \)可表示为
A=p_1^{(B_c_1)}_p_2^{(B_c_2)_p_3^(B_c_3)}_..._p_n^(B_c_n)
则\( A^B \)所有约数和为
(1+p_1+p_1^2+...+p_1^(B_c_1))_

质因数分解

代码

发表评论

textsms
account_circle
email

冒泡ioa

[poj1845]Sumdiv
题目 题目描述 Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901). 输入 …
扫描二维码继续阅读
2018-10-01