九州大学 1998年度
文系数学 第3問(c)

解答

(1)

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

であるから、出力は $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}$ と素因数分解すると、約数の和は

である。各 $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$ は

である。これらに2のべき乗を掛けて50以下に収めると $9,18,36,25,50,49$ を得る。したがって求める自然数は $9,18,25,36,49,50$ である。