問題一覧 > 教育的問題

No.3022 Linear Equation in One Variable mod 1000000000

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 50
作問者 : 👑 p-adic / テスター : hiro1729
お気に入りにしたユーザー ProblemId : 9256 / 自分の提出
問題文最終更新日: 2025-02-15 10:16:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 456 オムニバス (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。