/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
整数 N,M,A,B が与えられます。
整数列 X=(X_0,X_1,\ldots,X_{N-1}) を \displaystyle X_k = (Ak+B) \bmod M として定義します。
X_k > k を満たす 0 以上 N 未満の整数 k の個数を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 3\times 10^5
- 1\le N \le M\le 10^9
- 0\le A,B < M
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M A B
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
4 4 6 4 3 7 7 3 1 10 46 0 12 443 2026 131 210
出力例 1
2 3 10 395
1 つ目のテストケースについて考えます。
- k=0 のとき： X_0=(4\times 0+3)\bmod 6=3 なので、 X_k>k が成立します。
- k=1 のとき： X_1=(4\times 1+3)\bmod 6=1 なので、 X_k>k は成立しません。
- k=2 のとき： X_2=(4\times 2+3)\bmod 6=5 なので、 X_k>k が成立します。
- k=3 のとき： X_3=(4\times 3+3)\bmod 6=3 なので、 X_k>k は成立しません。
以上より、X_k>k が成立する 0 以上 4 未満の整数 k は k=0,2 の 2 個です。したがって、 1 行目には 2 を出力してください。
Score : 575 points
Problem Statement
You are given integers N,M,A,B.
Define an integer sequence X=(X_0,X_1,\ldots,X_{N-1}) as \displaystyle X_k = (Ak+B) \bmod M.
Find the number of integers k satisfying 0 \le k < N and X_k > k.
You are given T test cases; solve each of them.
Constraints
- 1\le T\le 3\times 10^5
- 1\le N \le M\le 10^9
- 0\le A,B < M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M A B
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
4 4 6 4 3 7 7 3 1 10 46 0 12 443 2026 131 210
Sample Output 1
2 3 10 395
Consider the first test case.
- When k=0: X_0=(4\times 0+3)\bmod 6=3, so X_k>k holds.
- When k=1: X_1=(4\times 1+3)\bmod 6=1, so X_k>k does not hold.
- When k=2: X_2=(4\times 2+3)\bmod 6=5, so X_k>k holds.
- When k=3: X_3=(4\times 3+3)\bmod 6=3, so X_k>k does not hold.
From the above, the integers k satisfying 0 \le k < 4 and X_k>k are k=0,2, which is two integers. Thus, output 2 on the first line.