POJ 1845-Sumdiv(快速冪取模+整數唯一分解定理+約數和公式+同余模公式)

POJ 1845-Sumdiv(快速冪取模+整數唯一分解定理+約數和公式+同余模公式)

 

Sumdiv Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 1845 Appoint description: System Crawler (2015-05-27)

Description

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).

Input

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

Output

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

Sample Input

2 3

Sample Output

15

Hint

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).

題意：求（A^B）的約數和對9901取余的結果。

 

思路：轉載--->優YoU