8993: [yosupo] Number Theory - Min of Mod of Linear
[Creator : ]
Description
Each test case consists of $T$ cases.
Given $N, M, A, B$. Print $\min\lbrace (Ax+B)\bmod M\mid 0\leq x < N\rbrace$.
Given $N, M, A, B$. Print $\min\lbrace (Ax+B)\bmod M\mid 0\leq x < N\rbrace$.
Input
$T$
$N_0$ $M_0$ $A_0$ $B_0$
$N_1$ $M_1$ $A_1$ $B_1$
:
$N_{T - 1}$ $M_{T - 1}$ $A_{T - 1}$ $B_{T - 1}$
$N_0$ $M_0$ $A_0$ $B_0$
$N_1$ $M_1$ $A_1$ $B_1$
:
$N_{T - 1}$ $M_{T - 1}$ $A_{T - 1}$ $B_{T - 1}$
Constraints
$1 \leq T \leq 10^5$
$1 \leq N, M \leq 10^9$
$0 \leq A, B < M$
$1 \leq N, M \leq 10^9$
$0 \leq A, B < M$
Sample 1 Input
14
1 13 10 11
2 13 10 11
3 13 10 11
4 13 10 11
5 13 10 11
6 13 10 11
7 13 10 11
8 13 10 11
9 13 10 11
10 13 10 11
100 13 10 11
31415 92653 58979 32384
31415 9265358 9793 2384
1000000000 1000000000 999999999 999999999
Sample 1 Output
11
8
5
2
2
2
2
2
0
0
0
1
24
0