UVa 374

From Algorithmist
Jump to: navigation, search

374 - Big Mod[edit]

Summary[edit]

A text book problem.

Explanation[edit]

We are asked to compute b^{p}{\bmod  m}. Using Repeated Squaring, we can calculate b^{p} efficiently, so long as the individual multiplications aren't expensive. Just our luck, the modulus in the expression will keep the final result low. We can use the relation that (x\times y){\bmod  m}=((x{\bmod  m})\times (y{\bmod  m})){\bmod  m} to keep the intermediate results small. Thus, we can use a basic integer to hold intermediate results, and never have to resort to BigNum multiplications.

Input[edit]

3
18132
17

17
1765
3

2374859
3029382
36123

Output[edit]

13
2
13195

Solutions[edit]