No.3022 Linear Equation in One Variable mod 1000000000
Problem Statement
Consider the following problem:
You are given $2$ integers $N, M$ as input.
$\displaystyle Nk+M \equiv 0 \pmod{10^9} $
Determine whether there exists a positive integer $k$ satisfying the above, and if one exists, find the minimum value of such $k$.
Here, for an integer $n$, $n \equiv 0 \pmod{10^9}$ means that $n$ is divisible by $10^9$.
A positive integer $T$ is given at the beginning of the input. Then answer $T$ problems.
Input
For each positive integer $t$ not exceeding $T$, let $N_t, M_t$ denote the input $N,M$ for the $t$-th problem.
Then, the input is given from standard input in $1 + T$ lines in the following format:
- Line $1$ contains $T$.
- For each positive integer $t$ not exceeding $T$, line $1 + t$ contains the input $N_t, M_t$ for the $t$-th problem, separated by a single-byte space.
$T$ $N_1$ $M_1$ $\vdots$ $N_T$ $M_T$
Constraints
The input satisfies the following constraints:
- $T$ is an integer satisfying $1 \leq T \leq 10^5$
- For any positive integer $t$ not exceeding $T$:
- $N_t$ is an integer satisfying $1 \leq N_t \leq 10^{18}$
- $M_t$ is an integer satisfying $1 \leq M_t \leq 10^{18}$
Output
For each positive integer $t$ not exceeding $T$, if there exists a positive integer $k$ satisfying
$\displaystyle N_t k+M_t \equiv 0 \pmod{10^9} $
print its minimum value on line $t$; otherwise, print -1 on line $t$.
Print a newline at the end.
Sample
Input
4 1 1 1 2 2 1 3 1
Output
999999999 999999998 -1 333333333
For the $1$st problem,
$\displaystyle k+1 \equiv 0 \pmod{10^9} $
has a positive integer solution $k$, and its minimum value is $999999999$.
For the $2$nd problem,
$\displaystyle k+2 \equiv 0 \pmod{10^9} $
has a positive integer solution $k$, and its minimum value is $999999998$.
For the $3$rd problem,
$\displaystyle 2k+1 \equiv 0 \pmod{10^9} $
has no positive integer solution $k$.
For the $4$th problem,
$\displaystyle 3k+1 \equiv 0 \pmod{10^9} $
has a positive integer solution $k$, and its minimum value is $333333333$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。