問題一覧 > 通常問題

No.2558 中国剰余定理

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 276
作問者 : loop0919loop0919 / テスター : deuteridayodeuteridayo 👑 AngrySadEightAngrySadEight Kyo_s_sKyo_s_s kusirakusirakusirakusira MagentorMagentor DeltaStructDeltaStruct bluebery1001bluebery1001 rotti_coderrotti_coder ragnaragna マベマス（mavemas_413）マベマス（mavemas_413） けんぴんけんぴん akiaki
1 ProblemId : 10159 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-30 18:43:43

問題文

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

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

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

$\mathrm{mod}$とは？

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

制約

  • $1 \leq A, B \leq 3000$
  • $A$ と $B$ は互いに素
  • $0 \leq a < A$
  • $0 \leq b < B$
  • 入力は全て整数

入力

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

$A$ $B$ $a$ $b$

出力

答えを出力せよ。

サンプル

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

$7$ を $3$ で割った余りは $1$ です。
$7$ を $5$ で割った余りは $2$ です。
よって、 $7$ は条件を満たします。$6$ 以下の非負整数は条件を満たさないため、 $7$ を出力します。

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

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

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