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

2026年5月25日出題

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

2. 

   $7$ で割り切れる正整数を日曜数と呼ぼう。

   日曜数 $a$, $b$ に対して、日曜数 $x$ が存在して $ax=b$ が成り立つとき、$a$ を $b$ の日曜約数と呼ぶ。日曜数 $a$ が日曜数 $b$ の日曜約数であれば、$a$ が $b$ の普通の意味での約数であるが、逆は一般に成り立たない。たとえば、$14$ は $42$ の普通の意味での約数だが日曜約数ではない。

   日曜数で日曜約数をもたないものを、日曜素数と呼ぶ。 日曜数が日曜素数である必要十分条件は、$49$がその日曜数の普通の意味での約数でないことである。 普通の意味での素数である日曜素数は $7$ だけである。

   日曜数 $a$ の日曜約数である日曜素数を、$a$ の日曜素因数と呼ぶ。便宜上、$a$ 自身が日曜素数の場合、$a$ は $a$ の日曜素因数であるとする。

   たとえば、$21$ は日曜素数であり、$10878=21\times 518$ が成り立つので、$21$ は $10878$ の日曜素因数のひとつである．また、$21$ は $21$ の日曜素因数である。

   日曜数は、1個以上の日曜素数の積として表すことができる。表し方は、順序の違いを無視しても、必ずしも一通りではない。たとえば、$10878=7\times 1554=14\times 777=21\times 518=42\times 259$ である。

   1.  $7$ 以上 $1048572$ 以下の日曜数について日曜素因数の一覧表を出力するプログラムを書け。

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

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

      10878: 7 14 21 42 259 518 777 1554

   ヒント1

   $1048572$ 以下の日曜素数は $128397$ 個ある。