No.2119 Generalized Hyakugo Genzan
Note
After the contest ended, kotatsugame_t pointed out the following on twitter regarding how the problem statement was written[1], and henkoudekimasu suggested that it should be corrected even after the contest had ended[2], so the statement has been corrected in line with these remarks:
- In competitive programming problem statements, as a rule, $[\textrm{mod} \ast]$ should not be used to denote mod; $\pmod{\ast}$ should be used instead.
- In competitive programming problem statements, as a rule, $[ \ ]$ should not be used to denote elements of a sequence; subscripts should be used instead.
- 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 posting an inappropriate problem statement out of ignorance of the customs of competitive programming.
While at it, I also changed some of the wording to improve readability. The problem itself has not changed.
Problem Statement
You are given as input a non-negative integer $N$, a positive integer $M$, a sequence $B$ of positive integers of length $M$, and a sequence $C$ of integers of length $M$.
For a sequence $a$ and a non-negative integer $m$ less than its length, let $a_m$ denote the $1+m$-th element of $a$. That is, using the ellipsis $\ldots$, $a$ is written as $(a_0,a_1,\ldots)$.
Determine whether there exists a non-negative integer $n$ not exceeding $N$ such that $n \equiv C_m \pmod{B_m}$ for every non-negative integer $m$ less than $M$, and if one exists, find the minimum such value.
Input
The input is given from standard input in $2 + M$ lines in the following format:- Line $1$ contains $N$.
- Line $2$ contains $M$.
- For each non-negative integer $m$ less than $M$, line $3 + m$ contains $B_m, C_m$ separated by a single-byte space.
Constraints
The input satisfies the following constraints:
- $N$ is a non-negative integer not exceeding $10^5$
- $M$ is a positive integer not exceeding $10^5$
- For every non-negative integer $m$ less than $M$, $B_m$ is a positive integer not exceeding $10^5$
- For every non-negative integer $m$ less than $M$, $C_m$ is an integer between $-10^5$ and $10^5$, inclusive
Output
If there exists a non-negative integer $n$ not exceeding $N$ such that $n \equiv C_m \pmod{B_m}$ for every non-negative integer $m$ less than $M$, print the minimum such value on $1$ line; otherwise, print NaN.
Print a newline at the end.
Sample
Sample 1
Input
10 1 1 2
Output
0
The minimum non-negative integer $n$ not exceeding $10$ that satisfies $n \equiv 2 \pmod{1}$ is $0$.
Sample 2
Input
100 2 6 3 4 2
Output
NaN
Among the non-negative integers $n$ not exceeding $100$, the system of congruences
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle n &\displaystyle \equiv &\displaystyle 3 \pmod{6} \\ \displaystyle n &\displaystyle \equiv &\displaystyle 2 \pmod{4} \end{array} \right. $
has no solution.
Sample 3
Input
1000 3 3 8 5 4 7 -8
Output
104
A non-negative integer $n$ satisfying the system of congruences
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle n &\displaystyle \equiv &\displaystyle 8 \pmod{3} \\ \displaystyle n &\displaystyle \equiv &\displaystyle 4 \pmod{5} \\ \displaystyle n &\displaystyle \equiv &\displaystyle -8 \pmod{7} \end{array} \right. $
is, for example,
$\displaystyle C_0 \times 70 + C_1 \times 21 + C_2 \times 15 = 8 \times 70 + 4 \times 21 + (-8) \times 15 = 524 $
and the non-negative integer obtained by subtracting
$\displaystyle \textrm{lcm}(B_0,B_1,B_2) = \textrm{lcm}(3,5,7) = 105 $
from it as many times as possible, namely $104$, is the minimum such $n$. This calculation procedure is the origin of the name Hyakugo Genzan that appears in the title. Since $104$ is also a non-negative integer not exceeding $1000$, it is the minimum non-negative integer solution not exceeding $1000$.
Sources
These are the sources of the remarks mentioned in the Note.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。