問題一覧 > 教育的問題

No.2119 Generalized Hyakugo Genzan

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 66
作問者 : 👑 p-adic / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 8626 / 自分の提出
問題文最終更新日: 2023-02-27 18:06:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 367 (順位表) の他の問題:

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.

  1. Tweet by kotatsugame_t
  2. Tweet by henkoudekimasu

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