The Final Problem
All submissions for this problem are available.
Sherlock and Moriarty have come face to face. Moriarty claims he holds the key to unlock anything in the world, and given Sherlock a challenge to find the key. Sherlock, from his obvious-to-him inferences has found the information below. Help him find the key.
Given NUM, K, C and M, output the sum (modulo M) of (d^K + C) where d is a positive integer in the range [1,N] and N when divided by d gives a remainder of zero. Since N can be huge,it is given in the form of NUM pairs of positive integers P[i], ALPHA[i], where P[i] is a prime and ALPHA[i] is the power of P[i] in the prime factorisation of N.
Thus, N = P^ALPHA * P^ALPHA * … * P[num]^ALPHA[num]
A single line containing four positive integers, NUM K C M
The next num lines each contain two positive integers, P[i] and ALPHA[i]
A single line containing the required sum
- 1 ≤ NUM ≤ 500
- 1 ≤ K ≤ 5
- 1 ≤ ALPHA[i] ≤ 109
- 1 ≤ P[i] ≤ 1000
- 1 ≤ M ≤ 1000
- 1 ≤ C ≤ 1000
Input: 2 2 1 1000 5 1 2 1 Output: 134
|Time Limit:||- 1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.