쉬운 숙제

시간 제한1.5초메모리 제한256 MB

요약

수열 f(n)=A·f(n-1)+f(n-2)에서 f(n)을 p로 나눈 나머지가 x인 n이 L부터 R까지 몇 개인지 구합니다.

난이도: 어려움10점 중 8점
유형: 정수론, 행렬, 수학
정답자: 아직 제출이 없습니다

문제

정수 $A$ 를 하나 고정한다. 수열 $\{f(n)\}$ 은 다음 두 조건을 만족한다.

$f(0) = 0$ , $f(1) = 1$
1보다 큰 모든 정수 $n$ 에 대해 $f(n) = A \cdot f(n - 1) + f(n - 2)$

소수 $p$ 와 정수 $x$ ( $0 \leq x \leq p$ )가 주어진다. $L \leq n \leq R$ 을 만족하는 정수 $n$ 중에서 $f(n) \bmod p = x$ 인 $n$ 의 개수를 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ ( $1 \leq T \leq 42$ )가 주어진다.

이후 $T$ 개의 줄에 다섯 정수 $A$ , $p$ , $x$ , $L$ , $R$ 이 주어진다. ( $0 \leq A < 10^{9}$ , $2 < p < 10^{9}$ , $0 \leq x < p$ , $1 \leq L \leq R \leq 10^{18}$ ) $p$ 는 소수임이 보장된다.

출력

$T$ 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에는 $i$ 번째 테스트 케이스의 답을 출력한다.

예제1

예제 1
입력
```
2
1 5 0 1 5
2 29 12 3 6
```
예상 출력
```
1
2
```