MODPOW - Calculating very big numbers very quickly
Given numbers A, B, C, calculate (A to the power of B) mod C.
Input
The first line will contain an integer x, the number of test cases. x lines follow, each with three integers A, B, and C, the A, B, and C mentioned above.
Conditions:
A is no more than 1e5
B is no more than 1e18
C is no more than 1e7
Output
For each test case, print (A^B) mod C.
Example
Input: 1
1 1 2
Output: 1
hide comments
hendrik:
2011-09-13 19:22:14
yet another a^b%c. There are too many of them. See for example FASTPOW. |
Added by: | hua |
Date: | 2011-09-12 |
Time limit: | 1.465s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Alex Anderson |