시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 31 | 14 | 12 | 42.857% |
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
.
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
.
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
.
5 2 1 2 1 3 1
2