No.2558 Chinese Remainder Theorem
タグ : / 解いたユーザー数 309
作問者 : 👑
Kyo_s_s
kusirakusira
Magentor
DeltaStruct
bluebery1001
rotti_coder
ragna
けんぴん
Problem Statement
Find the minimum non-negative integer $x$ that satisfies both of the following conditions.
- $x \ \mathrm{mod} \ A = a$
- $x \ \mathrm{mod} \ B = b$
It can be proved that such an $x$ exists under the constraints of the problem.
What is $\mathrm{mod}$?
$a \ \mathrm{mod} \ b$ denotes the remainder when $a$ is divided by $b$.
For example, $7 \ \mathrm{mod} \ 3 = 1$.
Constraints
- $1 \leq A, B \leq 3000$
- $A$ and $B$ are coprime
- $0 \leq a < A$
- $0 \leq b < B$
- All inputs are integers
Input
The input is given in the following format.
$A$ $B$ $a$ $b$
Output
Output the answer.
Sample
Sample 1
Input
3 5 1 2
Output
7
The remainder when $7$ is divided by $3$ is $1$.
The remainder when $7$ is divided by $5$ is $2$.
Therefore, $7$ satisfies the conditions. Non-negative integers less than or equal to $6$ do not satisfy the conditions, so output $7$.
Sample 2
Input
1 3000 0 0
Output
0
Sample 3
Input
998 2443 5 3
Output
2203589
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。