No.2117 Introduction to the Chinese Remainder Theorem
p-adicNote
After the contest ended, kotatsugame_t pointed out the following issues with how the problem statement was written on Twitter[1], and kotatsugame_t and henkoudekimasu suggested that it should be corrected even after the contest had ended[2][3], so the statement has been revised in line with these remarks:
- In competitive programming problem statements, as a rule, mod should be written using $\pmod{\ast}$ and not $[\textrm{mod} \ast]$.
- In competitive programming problem statements, as a rule, elements of a sequence should be written using subscripts and not $[ \ ]$.
- In competitive programming problem statements, as a rule, $[ \ ]$ should not be used with $2$ different meanings.
The exact content of these remarks and suggestions can be found in the sources at the bottom of the page.
I sincerely apologize to all participants for the discomfort caused by writing an inappropriate problem statement without knowing the conventions of competitive programming.
The problem itself has not been changed.
Problem Statement
You are given positive integers $B_0$ and $B_1$ and integers $C_0$ and $C_1$ as input.
Determine whether there exists a non-negative integer $n$ satisfying the system of congruences
$\displaystyle \left\{ \begin{array}{rcll} \displaystyle n &\displaystyle \equiv &\displaystyle C_0 &\displaystyle \pmod{B_0} \\ \displaystyle n &\displaystyle \equiv &\displaystyle C_1 &\displaystyle \pmod{B_1} \end{array} \right. $
and, if one exists, find the minimum such value.
Below is an explanation for those unfamiliar with congruences. (Click to open)
For integers $a$ and $n$, $n$ being a multiple of $a$ means that there exists an integer $k$ satisfying $n = ka$. Note that usage of the term "multiple" varies somewhat: depending on the literature, the case where $a$ is $0$ may be excluded, or only the case where $n$ and $a$ are positive may be considered.
For a positive integer $b$ and integers $n$ and $m$, $n \equiv m \pmod{b}$ means that $n - m$ is a multiple of $b$. Also, $n \equiv m \pmod{b}$ is read as "$n$ and $m$ are congruent modulo $b$". A formula using the equals sign is called an equation, whereas a formula using the congruence symbol $\equiv$ is called a congruence.
Input
The input is given from Standard Input in the following format:$B_0$ $C_0$ $B_1$ $C_1$
Line $1$ contains $B_0$ and $C_0$ separated by a single-byte space, and line $2$ contains $B_1$ and $C_1$ separated by a single-byte space.
Constraints
The input satisfies the following constraints:
- $B_0$ is a positive integer not greater than $100$
- $C_0$ is an integer between $-100$ and $100$, inclusive
- $B_1$ is a positive integer not greater than $100$
- $C_1$ is an integer between $-100$ and $100$, inclusive
Output
If there exists a non-negative integer $n$ satisfying the system of congruences
$\displaystyle \left\{ \begin{array}{rcll} \displaystyle n &\displaystyle \equiv &\displaystyle C_0 &\displaystyle \pmod{B_0} \\ \displaystyle n &\displaystyle \equiv &\displaystyle C_1 &\displaystyle \pmod{B_1} \end{array} \right. $
, print the minimum such value on $1$ line; if none exists, print NaN.
Print a newline at the end.
Sample
Sample 1
Input
1 3 2 4
As shown here, $C_0$ and $C_1$ may be greater than $B_0$ and $B_1$.
Output
0
$n = 0$ is the minimum non-negative integer solution of the system of congruences
$\displaystyle \left\{ \begin{array}{rcll} \displaystyle n &\displaystyle \equiv &\displaystyle 3 &\displaystyle \pmod{1} \\ \displaystyle n &\displaystyle \equiv &\displaystyle 4 &\displaystyle \pmod{2} \end{array} \right. $
.
Sample 2
Input
2 -1 3 -1
As shown here, $C_0$ and $C_1$ may be negative. If you have never handled remainders of negative integers, please be careful, as depending on the language the behavior may not be what you intend.
Output
5
$n = 5$ is the minimum non-negative integer solution of the system of congruences
$\displaystyle \left\{ \begin{array}{rcll} \displaystyle n &\displaystyle \equiv &\displaystyle -1 &\displaystyle \pmod{2} \\ \displaystyle n &\displaystyle \equiv &\displaystyle -1 &\displaystyle \pmod{3} \end{array} \right. $
.
Sample 3
Input
6 3 4 2
Output
NaN
For a non-negative integer $c$, suppose that $n = c$ satisfies the system of congruences
$\displaystyle \left\{ \begin{array}{rcll} \displaystyle n &\displaystyle \equiv &\displaystyle 3 &\displaystyle \pmod{6} \\ \displaystyle n &\displaystyle \equiv &\displaystyle 2 &\displaystyle \pmod{4} \end{array} \right. $
. Then, since $c$ and $c \% (B_0 B_1)$ are congruent modulo $B_0 = 6$ and modulo $B_1 = 4$, $n = c \% (B_0 B_1)$ is also a solution of this system of congruences. Therefore, if this system of congruences has even $1$ non-negative integer solution, then, more strongly, it also has a non-negative integer solution less than $B_0 B_1 = 6 \times 4 = 24$.
However, by checking for each non-negative integer less than $24$ whether it is a solution of this system of congruences, we find that this system of congruences has no non-negative integer solution less than $24$. Therefore, this system of congruences does not have even $1$ non-negative integer solution.
Sources
These are the sources of the remarks mentioned in the Note.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。