2024年度「プログラミング言語1」「プログラミング言語演習」のページ

（ACM/ICPC 2008年日本国内予選問題B 改題）

$7$ で割った余りが $1$ である正整数は7⁢ℕ+1数と呼ばれる。しかし，発音しにくいので，月曜数と呼ぼう。

月曜数 $a$, $b$ に対して、月曜数 $x$ が存在して $ax=b$ が成り立つとき、$a$ を $b$ の月曜約数と呼ぶ。月曜数 $a$ が月曜数 $b$ の月曜約数であるためには、$a$ が $b$ の普通の意味の約数であれば必要十分であると、簡単に証明できる。

$1$ より大きな月曜数でそれ自身と $1$ の他に月曜約数をもたないものを、月曜素数と呼ぶ。普通の意味の素数である月曜数は月曜素数であるが、逆は一般に成り立たない。たとえば，$22$ は普通の意味の素数ではないが、月曜素数である。

月曜数 $a$ の月曜約数である月曜素数を、$a$ の月曜素因数と呼ぶ。たとえば、$22$ は月曜素数であり、$10648=22\times 484$ が成り立つので、$22$ は $10648$ の月曜素因数のひとつである．

$1$ より大きなどんな月曜数も、1個以上の月曜素数の積として表すことができる。表し方は、順序の違いを無視しても、必ずしも一通りではない。たとえば、$10648=8\times 1331=22\times 22\times 22$ である。

1.  $8$ から $1048573$ までの月曜数について月曜素因数の一覧表を出力するプログラムを書け。

   出力は、小さい月曜数から順に行うものとする。まず、月曜数を表示し，つづけて同じ行にコロン「:」、そして、月曜素因数の並びを、それぞれの前に空白を置いて、小さい順に重複なく表示する。該当の月曜数を複数回割る月曜素因数も1回だけ出力する。

   出力する表のうち、たとえば、$10648$ に対応する行は、次のようになる。

   10648: 8 22 1331

ヒント1

$1048573$ 以下の月曜素数は $86969$ 個ある。

ヒント2

ある月曜数 $a$ の月曜素因数をすべて出力するには、$a$ より小さなすべての月曜素数 $p$ について $a$ を $p$ で割ってみて割り切れたら出力すればうまくいきます。そのためには、事前に月曜素数の表を作っておけば楽です。

 $a+bi$ （ただし、$a$ と $b$ は整数、$i$ は虚数単位）の形で表せる複素数をガウス整数と呼ぶ。ガウス整数とガウス整数の積はガウス整数となる。ガウス整数 $a+bi$ でガウス整数 $m+ni$ が割り切れるとは、あるガウス整数 $x+yi$ が存在して、$(a+bi)(x+yi)=m+ni$ が成り立つことと定義する。

ガウス整数は以下の四種類に分類できる。

零

任意のガウス整数で割り切れる。

単数

ちょうど4個のガウス整数で割り切れる。

ガウス素数

ちょうど8個のガウス整数で割り切れる。

ガウス合成数

8個より多くのガウス整数で割り切れる。

1. ガウス整数の積を計算するプログラムを書け。整数 $a$, $b$, $m$, $n$ を入力し、 $(a+bi)(m+ni)=p+qi$ となる整数 $p$, $q$ を求めて出力せよ。

ヒント1

$i^2=\mathrm{-1}$

2. ガウス整数でガウス整数が割り切れるかを判定するプログラムを書け。整数 $a$, $b$, $m$, $n$ を入力し、$a+bi$ で $m+ni$ が割り切れるときは Oui と、そうでないときは Non と出力せよ。

ヒント2

ガウス整数のことをいったん忘れて複素数の範囲で計算すると、 $$\begin{array}{ccc}\frac{m+ni}{a+bi}& =& \frac{(a-bi)(m+ni)}{(a-bi)(a+bi)}\\ & =& \frac{am+bn}{a^2+b^2}+\frac{an-bm}{a^2+b^2}i\end{array}$$ となる。ここでガウス整数のことを思い出すと、$\frac{m+ni}{a+bi}$ がガウス整数である必要十分条件は、 $\frac{am+bn}{a^2+b^2}$ も $\frac{an-bm}{a^2+b^2}$ も普通の意味の整数であることだとわかる。 したがって、$a+bi$ で $m+ni$ が割り切れる必要十分条件は、$am+bn$ も $an-bm$ も $a^2+b^2$ で割り切れることである。

3. ガウス整数を分類するプログラムを書け。整数 $a$, $b$ を入力し、$a+bi$ の種類に応じて、以下の通り出力せよ。

   種類	出力
   零	Z
   単数	U
   ガウス素数	P
   ガウス合成数	C

ヒント3

ガウス整数 $m+ni$ の分類と $m^2+n^2$ の値には、以下の関係がある。

• $m^2+n^2=0$ ならば、 $m+ni$ は零である。
• $m^2+n^2=1$ ならば、 $m+ni$ は単数である。
• $m^2+n^2>1$ ならば、 $m+ni$ はガウス素数であるか、ガウス合成数である。

ガウス整数 $a+bi$, $x+yi$, $m+ni$ が $(a+bi)(x+yi)=m+ni$ をみたせば、 $(a^2+b^2)(x^2+y^2)=m^2+n^2$ が成り立つ。 さらに $m+ni\ne 0$ を仮定すると、 $1\le a^2+b^2\le m^2+n^2$ が成り立つ。

ヒント4

ガウス整数 $m+ni$ が零でも単数でもなければ、$m+ni$ を割り切るガウス整数は少なくとも八つある。うち四つは単数であり、残りの四つは $m+ni$ に単数をかけたものである。零でも単数でもないガウス整数 $m+ni$ を割り切るガウス整数がその八つ以外になければ $m+ni$ はガウス素数であり、あればガウス合成数である。

この事実を利用すると、零でも単数でもないガウス整数 $m+ni$ がガウス素数であるかどうかの判定には、 $1<a^2+b^2<m^2+n^2$ をみたすガウス整数 $a+bi$ でのみ試し割りをすれば良いことがわかる。すなわち、 $m+ni$ が $1<a^2+b^2<m^2+n^2$ をみたすどのガウス整数 $a+bi$ でも割り切れなければガウス素数であり、どれか一つででも割り切れればガウス合成数である。

ヒント5（高速化を望む人のために）

1. ガウス整数 $a+bi$ と $a^{\prime }+b^{\prime }i$ について、ある単数 $u+vi$ が存在して $(a+bi)(u+vi)=a^{\prime }+b^{\prime }i$ が成り立つとき、ガウス整数 $a+bi$ でガウス整数 $m+ni$ が割り切れることと、ガウス整数 $a^{\prime }+b^{\prime }i$ でガウス整数 $m+ni$ が割り切れることは同値である。

   ガウス整数 $a+bi$ が零でなければ、ある単数 $u+vi$ が存在して $(a+bi)(u+vi)=a^{\prime }+b^{\prime }i$ が成り立つガウス整数 $a^{\prime }+b^{\prime }i$ は、ちょうど四つあり、そのうち、ちょうど一つが $a^{\prime }>0$ かつ $b^{\prime }\ge 0$ をみたす。

2. ガウス整数 $m+ni$ がガウス整数 $a+bi$ と $a^{\prime }+b^{\prime }i$ で $m+ni=(a+bi)(a^{\prime }+b^{\prime }i)$ と書ければ、 ${(a^2+b^2)}^2\le m^2+n^2$ または ${({a^{\prime }}^2+{b^{\prime }}^2)}^2\le m^2+n^2$ が成り立つ。

以上の事実をうまく利用すると、 $a>0$ かつ $b\ge 0$ かつ ${(a^2+b^2)}^2\le m^2+n^2$ をみたすガウス整数 $a+bi$ でのみ試し割りすることで、高速化が可能である。

ヒント6（さらに高速化を望み、数学が得意で、英語が苦にならない人のために）

Weisstein, Eric W. "Gaussian Prime." From MathWorld--A Wolfram Web Resource に、ガウス整数がガウス素数である必要十分条件が説明されている。

ヒント7

ガウス整数の分類表

余談1

「ガウス整数」は数学者ヨハン・カール・フリードリヒ・ガウスにちなんで名付けられた。

自慢1

出題者はガウスの弟子の弟子の弟子の弟子の弟子の弟子の弟子の弟子の弟子の弟子です。

 $a+b\omega$ （ただし、$a$ と $b$ は整数、$\omega =(-1+\sqrt{3}i)⁄2$ ）の形で表せる複素数をアイゼンシュタイン整数と呼ぶ。アイゼンシュタイン整数とアイゼンシュタイン整数の積はアイゼンシュタイン整数となる。アイゼンシュタイン整数 $a+b\omega$ でアイゼンシュタイン整数 $m+n\omega$ が割り切れるとは、あるアイゼンシュタイン整数 $x+y\omega$ が存在して、$(a+b\omega )(x+y\omega )=m+n\omega$ が成り立つことと定義する。

アイゼンシュタイン整数は以下の四種類に分類できる。

零

任意のアイゼンシュタイン整数で割り切れる。

単数

ちょうど6個のアイゼンシュタイン整数で割り切れる。

アイゼンシュタイン素数

ちょうど12個のアイゼンシュタイン整数で割り切れる。

アイゼンシュタイン合成数

12個より多くのアイゼンシュタイン整数で割り切れる。

1. アイゼンシュタイン整数の積を計算するプログラムを書け。整数 $a$, $b$, $m$, $n$ を入力し、 $(a+b\omega )(m+n\omega )=p+q\omega$ となる整数 $p$, $q$ を求めて出力せよ。

ヒント1

${\omega }^2=-1-\omega$

2. アイゼンシュタイン整数でアイゼンシュタイン整数が割り切れるかを判定するプログラムを書け。整数 $a$, $b$, $m$, $n$ を入力し、$a+b\omega$ で $m+n\omega$ が割り切れるときは Ja と、そうでないときは Nein と出力せよ。

ヒント2

アイゼンシュタイン整数のことをいったん忘れて複素数の範囲で計算すると、 $$\begin{array}{ccc}\frac{m+n\omega }{a+b\omega }& =& \frac{(a-b-b\omega )(m+n\omega )}{(a-b-b\omega )(a+b\omega )}\\ & =& \frac{am-bm+bn}{a^2-ab+b^2}+\frac{an-bm}{a^2-ab+b^2}\omega \end{array}$$ となる。ここでアイゼンシュタイン整数のことを思い出すと、$\frac{m+n\omega }{a+b\omega }$ がアイゼンシュタイン整数である必要十分条件は、 $\frac{am-bm+bn}{a^2-ab+b^2}$ も $\frac{an-bm}{a^2-ab+b^2}$ も普通の意味の整数であることだとわかる。 したがって、$a+b\omega$ で $m+n\omega$ が割り切れる必要十分条件は、$am-bm+bn$ も $an-bm$ も $a^2-ab+b^2$ で割り切れることである。

3. アイゼンシュタイン整数を分類するプログラムを書け。整数 $a$, $b$ を入力し、$a+b\omega$ の種類に応じて、以下の通り出力せよ。

   種類	出力
   零	Z
   単数	U
   アイゼンシュタイン素数	P
   アイゼンシュタイン合成数	C

ヒント3

アイゼンシュタイン整数 $m+n\omega$ の分類と $m^2-mn+n^2$ の値には、以下の関係がある。

• $m^2-mn+n^2=0$ ならば、 $m+n\omega$ は零である。
• $m^2-mn+n^2=1$ ならば、 $m+n\omega$ は単数である。
• $m^2-mn+n^2>1$ ならば、 $m+n\omega$ はアイゼンシュタイン素数であるか、アイゼンシュタイン合成数である。

アイゼンシュタイン整数 $a+b\omega$, $x+y\omega$, $m+n\omega$ が $(a+b\omega )(x+y\omega )=m+m\omega$ をみたせば、 $(a^2-ab+b^2)(x^2-xy+y^2)=m^2-mn+n^2$ が成り立つ。 さらに $m+n\omega \ne 0$ を仮定すると、 $1\le a^2-ab+b^2\le m^2-mn+n^2$ が成り立つ。

ヒント4

アイゼンシュタイン整数 $m+n\omega$ が零でも単数でもなければ、$m+n\omega$ を割り切るアイゼンシュタイン整数は少なくとも十二個ある。うち六つは単数であり、残りの六つは $m+n\omega$ に単数をかけたものである。零でも単数でもないアイゼンシュタイン整数 $m+n\omega$ を割り切るアイゼンシュタイン整数がその十二個以外になければ $m+n\omega$ はアイゼンシュタイン素数であり、あればアイゼンシュタイン合成数である。

この事実を利用すると、零でも単数でもないアイゼンシュタイン整数 $m+n\omega$ がアイゼンシュタイン素数であるかどうかの判定には、 $1<a^2-ab+b^2<m^2-mn+n^2$ をみたすアイゼンシュタイン整数 $a+b\omega$ でのみ試し割りをすれば良いことがわかる。すなわち、 $m+n\omega$ が $1<a^2-ab+b^2<m^2-mn+n^2$ をみたすどのアイゼンシュタイン整数 $a+b\omega$ でも割り切れなければアイゼンシュタイン素数であり、どれか一つででも割り切れればアイゼンシュタイン合成数である。

ヒント5（高速化を望む人のために）

1. アイゼンシュタイン整数 $a+b\omega$ と $a^{\prime }+b^{\prime }\omega$ について、ある単数 $u+v\omega$ が存在して $(a+b\omega )(u+v\omega )=a^{\prime }+b^{\prime }\omega$ が成り立つとき、アイゼンシュタイン整数 $a+b\omega$ でアイゼンシュタイン整数 $m+n\omega$ が割り切れることと、アイゼンシュタイン整数 $a^{\prime }+b^{\prime }\omega$ でアイゼンシュタイン整数 $m+n\omega$ が割り切れることは同値である。

   アイゼンシュタイン整数 $a+b\omega$ が零でなければ、ある単数 $u+v\omega$ が存在して $(a+b\omega )(u+v\omega )=a^{\prime }+b^{\prime }\omega$ が成り立つアイゼンシュタイン整数 $a^{\prime }+b^{\prime }\omega$ は、ちょうど六つあり、そのうち、ちょうど一つが $0\le b^{\prime }<a^{\prime }$ をみたす。

2. アイゼンシュタイン整数 $m+n\omega$ がアイゼンシュタイン整数 $a+b\omega$ と $a^{\prime }+b^{\prime }\omega$ で $m+n\omega =(a+b\omega )(a^{\prime }+b^{\prime }\omega )$ と書ければ、 ${(a^2-ab+b^2)}^2\le m^2-mn+n^2$ または ${({a^{\prime }}^2-a^{\prime }{b}^{\prime }+{b^{\prime }}^2)}^2\le m^2-mn+n^2$ が成り立つ。

以上の事実をうまく利用すると、 $0\le b<a$ かつ ${(a^2-ab+b^2)}^2\le m^2-mn+n^2$ をみたすアイゼンシュタイン整数 $a+b\omega$ でのみ試し割りすることで、高速化が可能である。

ヒント6（さらに高速化を望み、数学が得意で、英語が苦にならない人のために）

Weisstein, Eric W. "Eisenstein Prime." From MathWorld--A Wolfram Web Resource に、アイゼンシュタイン整数がアイゼンシュタイン素数である必要十分条件が説明されている。

ヒント7

アイゼンシュタイン整数の分類表

余談1

「アイゼンシュタイン整数」は数学者フェルディナント・ゴットホルト・マックス・アイゼンシュタインにちなんで名付けられた。