LCPCP2 - Johnny Learns Modular exponentiation
After Johnny solved problem A in LCPC2012 practice contest he decided to read more about modulo operation so he read the following article.
Modular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography.
A "modular exponentiation" calculates the remainder when a positive integer b (the base) raised to the e-th power (the exponent), and the total quantity is divided by a positive integer m, called the modulus. In symbols, this is, given base b, exponent e, and modulus m, the modular exponentiation c is: c = (b^e) mod M
For example, given b = 5, e = 3, and m = 13, the solution c is the remainder of dividing 5^3 by 13, which is the remainder of 125 / 13, or 8.
If b, e, and m are non-negative, and b < m, then a unique solution c exists with the property 0 ≤ c < m.
Input
Input will start with T number of test cases. Followed by T test cases each test has three integers 0 < b < 109 and 0
Output
For each test case, output the result using the following format:
k. x
Where k is the test case number (starting at 1), a single period, a single space, then the answer x.
Sample
Input 1 3 2 8 Output 1. 1
hide comments
abd alkader:
2012-11-22 21:17:38
easy task remove it even from tutorial |
|
:D:
2012-10-06 23:07:30
Agree. Still it's a very good for tutorial, since you need to use fast multiplication, that is one of the basic building blocks in other problems. |
|
Francky:
2012-10-06 18:44:45
+1 with Alex, hide this one too, please.
|
|
Alex Anderson:
2012-10-06 17:59:48
I want to say this should go into tutorial, but there are already multiple problems in both classical and tutorial that are this exact thing (or harder). But it is part of a contest... eh, I dunno. But I don't think it should be worth any points on spoj. |
Added by: | Gareev |
Date: | 2012-10-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | LCPC 2012 |