問題一覧 > 教育的問題

No.2117 中国剰余定理入門

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 121
作問者 : 👑 p-adic / テスター : 遭難者
0 ProblemId : 8621 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-06 21:38:01

注

コンテスト終了後にtwitterでkotatsugame_tさんより問題文の書き方に関する以下のご指摘をいただき[1]、kotatsugame_tさんおよびhenkoudekimasuさんよりコンテスト終了後でも修正すべきとのご示唆をいただきました[2][3]のでご指摘に沿うように修正いたしました：

  • 競技プログラミングの問題文においてはmodの表記に原則 [mod∗][\textrm{mod} \ast] を使うべきでなく(mod∗)\pmod{\ast} を使うべきである。
  • 競技プログラミングの問題文においては数列の成分の表記に原則 [ ][ \ ] を使うべきでなくsubscriptを使うべきである。
  • 競技プログラミングの問題文においては原則 [ ][ \ ] を 22 種類の用法で用いるべきではない。

より正確なご指摘・ご示唆の内容はページ下部の出典からご確認いただけます。

この度は競技プログラミングの慣習を知らずに不適切な問題文を記載してしまい参加者の皆様に不快な思いをさせてしまったことを心からお詫び申し上げます。

なお問題の内容自体に変更はございません。

問題文

入力に正整数 B0B_0 と B1B_1 と整数 C0C_0 と C1C_1 が与えられます。

　

連立合同式

{n≡C0(modB0)n≡C1(modB1)\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.

を満たす非負整数 nn が存在するか否かを判定し、存在する場合はその最小値を求めてください。

　

以下、合同式を知らない人向けの説明をします。（クリックで開く）

　

整数 aa と nn に対し、nn が aa の倍数であるとは、n=kan = ka を満たす整数 kk が存在するということです。ただし文献によっては aa が 00 の場合を除いたり nn や aa が正の場合のみ考えたりなど、倍数という用語にはやや流儀の幅があります。

正整数 bb と整数 nn と mm に対し、n≡m(modb)n \equiv m \pmod{b} であるとは、n−mn - m が bb の倍数であるということです。また n≡m(modb)n \equiv m \pmod{b} は「bb を法として nn と mm は合同である」のように読みます。等号を使った数式は等式と呼ばれますが、合同の記号 ≡\equiv を使った数式は合同式と呼ばれます。

入力

入力は次の形式で標準入力から与えられます： 
B0B_0 C0C_0
B1B_1 C1C_1

11 行目に B0B_0 と C0C_0 が半角空白区切りで与えられ、22 行目に B1B_1 と C1C_1 が半角空白区切りで与えられます。

制約

入力は以下の制約を満たします：

  • B0B_0 は 100100 以下の正整数
  • C0C_0 は −100-100 以上 100100 以下の整数
  • B1B_1 は 100100 以下の正整数
  • C1C_1 は −100-100 以上 100100 以下の整数

出力

連立合同式

{n≡C0(modB0)n≡C1(modB1)\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.

を満たす非負整数 nn が存在する場合はその最小値を 11 行に出力し、存在しない場合はNaNと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1 3
2 4

このように C0C_0 や C1C_1 が B0B_0 や B1B_1 より大きいこともあります。

出力
0

n=0n = 0 は連立合同式

{n≡3(mod1)n≡4(mod2)\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.

の最小の非負整数解です。

サンプル2
入力
2 -1
3 -1

このように C0C_0 や C1C_1 が負であることもあります。負の整数に対する剰余を扱ったことがない人は、言語によっては意図通りの挙動にならないかもしれないのでご注意ください。

出力
5

n=5n = 5 は連立合同式

{n≡−1(mod2)n≡−1(mod3)\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.

の最小の非負整数解です。

サンプル3
入力
6 3
4 2
出力
NaN

非負整数 cc に対し、n=cn = c が連立合同式

{n≡3(mod6)n≡2(mod4)\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.

を満たすと仮定すると、B0=6B_0 = 6 や B1=4B_1 = 4 を法として cc と c%(B0B1)c \% (B_0 B_1) が合同であることから n=c%(B0B1)n = c \% (B_0 B_1) もまたこの連立合同式の解となります。従ってこの連立合同式が非負整数解を 11 つでも持つならば、より強く B0B1=6×4=24B_0 B_1 = 6 \times 4 = 24 未満の非負整数解も持つことが分かります。

ところが 2424 未満の各非負整数に対しそれがこの連立合同式の解であるか否かを調べることで、この連立合同式が 2424 未満の非負整数解を持たないことが分かります。従って、この連立合同式は非負整数解を 11 つも持ちません。

出典

注に記載させていただいたご指摘内容の出典です。

  1. kotatsugame_tさんのtweet
  2. kotatsugame_tさんのtweet
  3. henkoudekimasuさんのtweet

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