ZOJ Problem Set - 3920
The divisor function σk(n) for n an integer is defined as the sum of the k-th powers of the (positive integer) divisors of n.
And f(n, m, k) is defined as the following:
where gcd(a, b) is the greatest common divisor of a and b.
You are given four integers N, M, X, C. Please calculate the value of gao3(N, M, X) mod C.
Input will consist of multiple test cases.
Let C = p1a1p2a2···pkak, where pi are distinct primes and ai ≥ 1. It's guaranteed that 1 ≤ ai < pi ≤ 100 and k ≤ 5 and piai ≤ 109.
One line for each case, you should output gao3(N, M, X) mod C.
2 2 1 1 1 3
Author: LIN, Xi
Source: ZOJ Monthly, February 2016