jtw7913   8달 전


문제

모듈로 연산 게임는 심심할 때 할 수 있는 게임입니다. 휴대폰 없이 종이만으로도 플레이할 수 있습니다.

먼저 정수 $m$을 하나 정합니다.
그 다음 두 개의 수열 $a_i$와 $b_i $를 정합니다.
마지막으로 시작 값 $s_0$를 정합니다.

이제 목표는 가능한 한 적은 횟수의 이동으로 $s_0$에서 0으로 만드는 것입니다.

각 이동에서는 어떤 인덱스 $i$를 하나 선택하고, 현재 값에 대해 다음 연산을 수행합니다:

$s_j = (s_{j-1} \times a_i + b_i) \mod m$

입력

  • 첫 번째 줄에 세 정수 $ m, n, s_0 $가 주어집니다.

    • $ 0 < m \le 1{,}000{,}000 $
    • $ 0 \le n \le 10 $
    • $ 0 < s_0 < m $
  • 다음 $ n $개의 줄에는 각각 두 정수 $ a_i, b_i $가 주어집니다.

    • $ 0 \le a_i \le 1{,}000{,}000{,}000 $
    • $ 0 \le b_i \le 1{,}000{,}000{,}000 $

출력

  • 시작 값 $ s_0 $에서 출발하여 0에 도달하기 위한 최소 이동 횟수를 출력하세요.
  • 만약 어떤 방법으로도 0에 도달할 수 없다면 -1을 출력하세요.

댓글을 작성하려면 로그인해야 합니다.