素数メニューのサムネイル
中国剰余定理 (paizaランク C 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

素数に関連した有名な定理として中国剰余定理という定理が存在します。その内容は次の通りです。

「m1 と m2 を互いに素な正の整数とする。

Z を m1 で割った余りが b1 であり、Z を m2 で割ったあまりが b2 であるような整数 Z が 0 以上 m1 × m2 未満にただ 1 つ存在する。」


なお、「m1 と m2 が互いに素である」とは、「m1 と m2 の最大公約数が 1 である」ことをいいます。
この定理が実際に成り立つかどうかをプログラミングで確認してみましょう。
上記の定理の m1 , m2 , b1 , b2 の値が与えられるので、これらに対応する 0 以上 m1 × m2 未満の整数 Z を求めてください。
中国剰余定理によって、m1 , m2 , b1 , b2 に対応する整数 Z が 0 以上 m1 × m2 未満に必ず 1 つ存在することが保証されています。

入力される値

m1 m2 b1 b2


・ 1 行で整数 m1 , m2 , b1 , b2 が半角スペース区切りで与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

与えられた整数について中国剰余定理で求まる整数 Z を 1 行で出力してください。
出力の末尾には改行を入れてください。

条件

・ 1 ≦ m1 , m2 ≦ 100,000
・ 0 ≦ b1 < m1
・ 0 ≦ b2 < m2

入力例1

5 6 2 3

出力例1

27

入力例2

100 101 10 11

出力例2

10010

問題一覧へ戻る

ページの先頭へ戻る