Problem D: Modulo Solitaire
Modulo Solitaire is a game that can be played when you are bored.
You can even play it without a phone, just on paper. First, you
pick a number m. Then you pick two sequences of numbers
ai and bi. Finally,
you pick a starting number s0. Now, your
goal is to go from s0 to 0 in as few moves
as possible. In each move, you choose an i, then
multiply your current number by ai,
add bi to it, and reduce the result
modulo m. That is, sj = (sj-1 * aij + bij) % m.
Input Specification
The first line of input contains three integers 0 < m <=
1000000, 0 <= n <= 10, and 0 < s0 < m.
The next n lines each contain two integers, a pair 0 <= ai <= 1000000000
and 0 <= bi <= 1000000000.
Sample Input
5 2 1
2 1
3 1
Output Specification
Output a single integer, the shortest number of moves needed to
reach 0 starting from s0. If it is not possible
to reach 0 in any number of moves, output -1.
Output for Sample Input
2
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.