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

2026年5月18日出題

1. 

    $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

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

2. 

    $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

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