問題一覧 > 通常問題

No.2558 中国剰余定理

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 290
作問者 : 👑 loop0919 / テスター : deuteridayo 👑 AngrySadEight Kyo_s_s kusirakusira Magentor DeltaStruct bluebery1001 rotti_coder ragna マベマス（mavemas_413） けんぴん aki
1 ProblemId : 10159 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:43:43

問題文

以下の条件をともに満たす非負整数 xx の最小値を求めてください。

  • x mod A=ax \ \mathrm{mod} \ A = a
  • x mod B=bx \ \mathrm{mod} \ B = b

ただし、問題の制約下で、そのような xx が存在することが証明できます。

mod\mathrm{mod}とは？

a mod ba \ \mathrm{mod} \ b は、 aa を bb で割った余りを指します。
例えば、7 mod 3=17 \ \mathrm{mod} \ 3 = 1 です。

制約

  • 1≤A,B≤30001 \leq A, B \leq 3000
  • AA と BB は互いに素
  • 0≤a<A0 \leq a < A
  • 0≤b<B0 \leq b < B
  • 入力は全て整数

入力

入力は以下の形式で与えられる。

AA BB aa bb

出力

答えを出力せよ。

サンプル

サンプル1
入力
3 5 1 2
出力
7

77 を 33 で割った余りは 11 です。
77 を 55 で割った余りは 22 です。
よって、 77 は条件を満たします。66 以下の非負整数は条件を満たさないため、 77 を出力します。

サンプル2
入力
1 3000 0 0
出力
0

サンプル3
入力
998 2443 5 3
出力
2203589

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