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

2025年5月26日出題

1. 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$ で割ってみて割り切れたら出力すればうまくいきます。そのためには、事前に月曜素数の表を作っておけば楽です。