28365번 - 점화식과 주기

문제

소수 $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)$ 중 사전순으로 가장 작은 것을 출력한다.

제한

• 0ドル < p \le 2147483647$
• 0ドル \le a, b, x_0, x_1 < p$

힌트