/ 
Time Limit: 8 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
整数 A,B,V,M が与えられます． ここで，A と B は互いに素であることが保証されます． また，あなたは整数 x を持っています． 最初，x=V です．
あなたは，以下の 4 種類の操作を好きな順序で好きな回数繰り返すことができます．
-
x の値を，x+A で置き換える．
-
x の値を，x-A で置き換える．
-
x の値を，x+B で置き換える．
-
x の値を，x-B で置き換える．
ただし，操作のどの瞬間においても，0 \leq x \leq M が成立している必要があります．
この条件の元で，x がとりうる値が何種類あるかを求めてください．
一つの入力ファイルにつき，T 個のテストケースを解いてください．
制約
- 1 \leq T \leq 10^5
- 1 \leq A < B \leq M \leq 10^9
- A と B は互いに素である．
- 0 \leq V \leq M
- 入力される値はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
T case_1 case_2 \vdots case_3
各ケースは以下の形式で与えられる．
A B V M
出力
各ケースについて答えを出力せよ．
入力例 1
5 3 5 0 5 1 2 5 10 5 8 4 9 10 99 48 106 500000000 500000001 123456789 900000000
出力例 1
4 11 4 10 800000002
1 つ目のテストケースでは，x=0,2,3,5 の 4 通りの値が考えられます．
Score : 1000 points
Problem Statement
Given are integers A, B, V, and M, where A and B are guaranteed to be coprime. Additionally, you have an integer x. Initially, x=V.
You can do the following four kinds of operations any number of times in any order.
-
Replace the value of x with x+A.
-
Replace the value of x with x-A.
-
Replace the value of x with x+B.
-
Replace the value of x with x-B.
Here, 0 \leq x \leq M must hold at any moment during this process.
Under this condition, find how many different values x can take.
For each input file, solve T test cases.
Constraints
- 1 \leq T \leq 10^5
- 1 \leq A < B \leq M \leq 10^9
- A and B are coprime.
- 0 \leq V \leq M
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_3
Each case is in the following format:
A B V M
Output
Print the answer for each case.
Sample Input 1
5 3 5 0 5 1 2 5 10 5 8 4 9 10 99 48 106 500000000 500000001 123456789 900000000
Sample Output 1
4 11 4 10 800000002
In the first case, x can take four values: x=0,2,3,5.