UVa 374

From Algorithmist
Jump to navigation Jump to search

374 - Big Mod[edit]

Summary[edit]

A text book problem.

Explanation[edit]

We are asked to compute . Using Repeated Squaring, we can calculate 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 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]