九州大学 1998年度 前期日程 第2次学力試験 整数・場合の数文系数学 第3問(c)

(1)

30行目で $$M=2\mathrm{INT}(N\mathrm{/}2)+1$$ としているので、40行目から80行目のループでは $K=1,3,5,\dots$ という奇数だけを調べる。50行目の $$X=N-K\mathrm{INT}(N\mathrm{/}K)$$ は、$N$ を $K$ で割った余りである。したがって、70行目で加えられるのは $N$ を割り切る奇数 $K$ だけである。 $N=12$ の正の奇数約数は$$\begin{gathered} 1, \\ 3 \end{gathered}$$であるから、出力は $1+3=4$ である。

(2)

出力が1となるのは、正の奇数約数が1しかないときである。これは $N$ が奇数の素因数をもたないことと同値である。したがって $$N=2^r(r=0,1,2,\dots )$$ の形の自然数がすべて求める入力である。

(3) $N=2^{r}M$ と書く。ただし $M$ は奇数とする。プログラムの出力は $M$ の正の約数の和である。$M$ を $$M=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$$ と素因数分解すると、約数の和は$$(1+p_1+\cdots +p_1^{{\alpha }_1})(1+p_2+\cdots +p_2^{{\alpha }_2})\cdots (1+p_s+\cdots +p_s^{{\alpha }_s})$$である。各 $p_i$ は奇数なので、$1+p_i+\cdots +p_i^{{\alpha }_i}$ の偶奇は項数 ${\alpha }_i+1$ の偶奇で決まる。よって約数の和が奇数であるための条件は、すべての ${\alpha }_i$ が偶数、すなわち $M$ が平方数であることである。

出力が1より大きい奇数になるには、$M$ が1より大きい奇数平方数であればよい。$2\leqq N\leqq 50$ の範囲で、奇数平方数としてあり得る $M$ は$$\begin{gathered} 9, \\ 25, \\ 49 \end{gathered}$$である。これらに2のべき乗を掛けて50以下に収めると $9,18,36,25,50,49$ を得る。したがって求める自然数は $9,18,25,36,49,50$ である。

プログラムを奇数 $K$ の走査と読み、出力を $N$ の奇数約数の和と解釈する。約数を $d$ と $M\mathrm{/}d$ に組にする方法で、奇数約数の和が奇数となる条件を奇数部分が平方数であることへ直す。

(1)

40行目では $K=1,3,5,\dots$ を走査し、50行目の$$X=N-K\mathrm{INT}(N\mathrm{/}K)$$は $N$ を $K$ で割った余りである。したがって出力は $N$ の正の奇数約数の和である。$12$ の奇数約数は $1,3$ なので、出力は4である。

(2)

出力が1なら、奇数約数は1しかない。これは $N$ が2のべきであることと同値である。したがって$$N=2^r(r=0,1,2,\dots )$$である。

(3)

$N=2^{r}M$ とし、$M$ を奇数とする。出力は $M$ の全約数の和である。約数を $d$ と $M\mathrm{/}d$ に組にすると、異なる2数の組の和は偶数である。組にならない約数があるのは $d=M\mathrm{/}d$、すなわち $M$ が平方数のときだけであり、その中央の約数は奇数である。よって出力が奇数であることと $M$ が平方数であることは同値である。

$2\leqq N\leqq 50$ で、$M>1$ の奇数平方数は $9,25,49$ である。2のべき倍を50以下まで並べると$$9,18,36,25,50,49.$$したがって答えは$$9,18,25,36,49,50$$である。