시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 18 | 12 | 3 | 60.000% |
Let us fix an integer $A$. Consider a sequence $\{f(n)\}$ which satisfies the following two conditions:
Given a prime $p$ and an integer $x$ ($0 \leq x \leq p$), your task is to calculate $|\{n : L \leq n \leq R, \ f(n) \bmod p = x\}|$, that is, the number of indices $n$ between $L$ and $R$ such that $f(n) \bmod p = x$.
There are one or more test cases.
The first line of input contains an integer $T$, the number of test cases ($1 \leq T \leq 42)$.
Each of the next $T$ lines contains five integers $A$, $p$, $x$, $L$ and $R$ ($0 \leq A < 10^{9}$, $2 < p < 10^{9}$, $0 \leq x < p$, $1 \leq L \leq R \leq 10^{18}$). It is guaranteed that $p$ is prime.
Print $T$ lines, one for each test case, containing the answers to the problem.
2 1 5 0 1 5 2 29 12 3 6
1 2