【選択問題】(第3問～第6問から2問選択)
問題編
問題
$\def\myBox#1{\bbox[3px, border:2px solid]{\ \bf{ #1 }\ }}\def\mybox#1{\bbox[4px, border:1px solid gray]{\ #1\ }}$p を $2$ 以上の自然数とする。 $0$ 以上 $p-1$ 以下の整数 a に対して、数の列 $b_1,b_2,\cdots,b_{p+1}$ を次のように定める。
- $b_1$ は a とする。
- $b_{k+1}$ は $a\times b_k+1$ を p で割った余りとする。ただし、 $k=1, 2, \cdots , p$ である。
さらに、 $b_1,b_2,\cdots,b_{p+1}$ を用いて、 $f(a)$ を次のように定める。
- $b_k=a$ となる k が $2\leqq k \leqq p+1$ の範囲にあるときは、そのような k の最小値を $f(a)$ とする。
- $b_k=a$ となる k が $2\leqq k \leqq p+1$ の範囲にないときは、 $f(a)=0$ とする。
もし $f(a)=p+1$ ならば、 $b_1,b_2,\cdots,b_p$ はすべて異なり、 $0$ 以上 $p-1$ 以下の p 個の整数が1回ずつ現れる。 p を入力して、 $a=0,1,\cdots,p-1$ に対して $f(a)$ の値を出力するプログラムを考えよう。
(1) $p=5,a=3$ としたとき、 $b_1=3$ であり、 $b_2$ は $3\times 3+1=10$ を5で割った余りであるので、 $b_2=0$ である。 $b_3$ は $3\times 0+1=1$ を5で割った余りであるので、 $b_3=1$ である。同様にして、 $b_4 = \myBox{ア}$, $b_5 = \myBox{イ}$, $b_6=0$ となる。したがって、 $f(3)$ の値は $\myBox{ウ}$ であることがわかる。
(2) 2以上のどのような自然数 p に対しても、 $f(0)$ の値は $\myBox{エ}$ であり、 $f(1)$ の値は $\myBox{オ}$ である。 $\myBox{エ}$, $\myBox{オ}$ に当てはまるものを、次の 0 ～ 5 のうちから一つずつ選べ。ただし、同じものを選んでもよい。
0: $0$
1: $1$
2: $2$
3: $p-1$
4: $p$
5: $p+1$(3) 2以上の自然数 p を入力して $f(0)$, $f(1)$, $\cdots$, $f(p-1)$ の値を出力する [プログラム1] を作成した。ただし、INT(X)はXを超えない最大の整数を表す関数である。
[プログラム1] 100 INPUT PROMPT "P=":P 110 FOR A=0 TO P-1 120 LET B=カ 130 FOR K=2 TO P+1 140 LET B=キ 150 IF B=A THEN 160 PRINT "f(";A;")=";ク 170 GOTO 210 180 END IF 190 NEXT K 200 PRINT "f(";A;")=0" 210 NEXT A 220 END[プログラム1] の $\myBox{カ}$, $\myBox{ク}$ に当てはまるものを、次の 0 ～ 5 のうちから一つずつ選べ。ただし、同じものを選んでもよい。
0: 0, 1: 1, 2: A
3: B, 4: K, 5: P$\myBox{キ}$ に当てはまるものを、次の 0 ～ 5 のうちから一つ選べ。
0: (B+1)-INT((B+1)/P)*P
1: (B+1)-INT((B+1)/P)*A
2: (A*B+1)-INT((A*B+1)/P)*P
3: (A*B+1)-INT((A*B+1)/A)*A
4: (A+1)-INT((A+1)/P)*B
5: (A+1)-INT((A+1)/P)*P(4) [プログラム1] を実行し、変数Pに9を入力したとき、出力される f(0), f(1), …, f(8) のうち、 f(2), f(3), …, f(8) の値は、次のようになる。
f(2)=3
f(3)=0
f(4)=$\myBox{ケ}$
f(5)=$\myBox{コ}$
f(6)=$\myBox{サ}$
f(7)=10
f(8)=3$\myBox{ケ}$, $\myBox{コ}$, $\myBox{サ}$ に当てはまるものを、次の 0 ～ b のうちから一つずつ選べ。ただし、同じものを繰り返し選んでもよい。
0: 0, 1: 1, 2: 2,
3: 3, 4: 4, 5: 5,
6: 6, 7: 7, 8: 8,
9: 9, a: 10, b: 11(5) 2以上の自然数 p に対して、 a を $0$ 以上 $p-1$ 以下の整数とするとき、 $f(a)=p+1$ である a の個数を求めたい。そのために、 [プログラム1] を変更して [プログラム2] を作成した。ただし、行番号に下線がひかれた行は、追加された行である。
[プログラム2] 100 INPUT PROMPT "P=":P 105 LET C=0 110 FOR A=0 TO P-1 120 LET B=カ 130 FOR K=2 TO P+1 140 LET B=キ 150 IF B=A THEN 160 PRINT "f(";A;")=";ク 165 IF シ THEN LET C=C+1 170 GOTO 210 180 END IF 190 NEXT K 200 PRINT "f(";A;")=0" 210 NEXT A 215 PRINT "個数は";C;"個である" 220 END[プログラム2]の $\myBox{シ}$ に当てはまるものを、次の 0 ～ 3 のうちから一つ選べ。
0: A=P+1
1: B=P+1
2: C=P+1
3: K=P+1[プログラム2]を実行し、変数Pに9を入力したとき、215行で出力される変数Cの値は $\myBox{ス}$ である。
考え方
一度説明を読んだだけではわかりにくいので、(1)で手を動かしながら説明文を理解しましょう。(2)では、 $a\times b_k+1$ がどうなるかを考えましょう。
(3)は説明文の変数とプログラム中の変数がどう対応しているかを把握してから考えましょう。また、余りは、INTを使って、「商×割る数」を元の数から引いて出します。よく使うテクニックです。
(4)は実際に書き出していきましょう。(5)は新しく追加された変数Cが何を表しているかを考えましょう。また、最後は、(2)と(4)で出した結果を使いましょう。 a の範囲に注意し、(4)だけを使っておしまい、としてはいけません。