問題一覧 > 教育的問題

No.3022 一元一次式 mod 1000000000

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : 👑 p-adicp-adic / テスター : hiro1729hiro1729
1 ProblemId : 9256 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-15 10:16:34

問題文

次のような問題を考えます:

入力に 22 個の整数 N,MN, M が与えられます。

Nk+M0(mod109)\displaystyle Nk+M \equiv 0 \pmod{10^9}

を満たす正整数 kk が存在するか否かを判定し、存在する場合はそのような kk の最小値を求めてください。

ただし整数 nn に対し n0(mod109)n \equiv 0 \pmod{10^9} とは nn10910^9 で割り切れるということを表します。

 

入力の最初に正整数 TT が与えられます。その後 TT 個の問題に答えてください。

入力

TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力 N,MN,MNt,MtN_t, M_t と置きます。

この時、入力は以下の形式で標準入力から 1+T1 + T 行で与えられます:

  • 11 行目に TT が与えられます。
  • TT 以下の各正整数 tt に対し、1+t1 + t 行目に tt 個目の問題に対する問題の入力 Nt,MtN_t, M_t が半角空白区切りで与えられます。
TT
N1N_1 M1M_1
\vdots
NTN_T MTM_T

制約

入力は以下の制約を満たします:

  • TT1T1051 \leq T \leq 10^5 を満たす整数
  • TT 以下の任意の正整数 tt に対し、
    • NtN_t1Nt10181 \leq N_t \leq 10^{18} を満たす整数
    • MtM_t1Mt10181 \leq M_t \leq 10^{18} を満たす整数

出力

TT 以下の各正整数 tt に対し、

Ntk+Mt0(mod109)\displaystyle N_t k+M_t \equiv 0 \pmod{10^9}

を満たす正整数 kk が存在する場合はその最小値を tt 行目に出力し、存在しない場合は-1tt 行目に出力してください。

最後に改行してください。

サンプル

入力
4
1 1
1 2
2 1
3 1
出力
999999999
999999998
-1
333333333

11個目の問題について、

k+10(mod109)\displaystyle k+1 \equiv 0 \pmod{10^9}

を満たす正整数 kk は存在し、その最小値は 999999999999999999 です。

 

22個目の問題について、

k+20(mod109)\displaystyle k+2 \equiv 0 \pmod{10^9}

を満たす正整数 kk は存在し、その最小値は 999999998999999998 です。

 

33 個目の問題について、

2k+10(mod109)\displaystyle 2k+1 \equiv 0 \pmod{10^9}

を満たす正整数 kk は存在しません。

 

44 個目の問題について、

3k+10(mod109)\displaystyle 3k+1 \equiv 0 \pmod{10^9}

を満たす正整数 kk は存在し、その最小値は 333333333333333333 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。