점화식과 주기

시간 제한0.5초메모리 제한512 MB

요약

소수 p에서 점화식 x_n = a*x_{n-1} + b*x_{n-2}의 수열이 S번째 항부터 주기 T로 반복되는 (S, T) 중 사전순으로 가장 작은 쌍을 구합니다.

문제

소수 $p$ 와 점화식 $x_n = ax_{n-1} + bx_{n-2}$ ( $n \ge 2$ ), 그리고 초항 $x_0$ , $x_1$ 이 정해지면, 다음 조건을 만족하는 정수 $S \ge 0$ , $T > 0$ 의 존재는 비둘기집의 원리에 따라 보장된다.

조건: 모든 $S$ 이상의 정수 $n$ 에 대해 $x_{n+T} - x_n$ 이 $p$ 의 배수이다.

문제는 위 조건을 만족하는 $(S, T)$ 중 사전순으로 가장 작은 것을 찾는 것이다.

첫째 줄에 정수 $p, a, b, x_0, x_1$ 가 주어진다. $p$ 는 소수임이 보장된다.

첫째 줄에 조건을 만족하는 $(S, T)$ 중 사전순으로 가장 작은 것을 출력한다.