千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2014年8月実施 専門 A5

标签：

• Programming-Basics

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Pascal プログラムを考える。

program test(input, output);
const MAX = 500;
var a: array[1..MAX] of integer;
    n, i, j: integer;
begin
  readln(n);
  for i := 1 to n do a[i] := 1;
  for i := 2 to n div 2 do begin
    j := 2*i;
    while j <= n do begin a[j] := a[j]+i; j := j+i end
  end;
  for i := 1 to n do
    if (i <= a[i]) and (a[i] <= n) then
      if a[a[i]] = i then writeln(i, a[i])
end.

(1) 入力が $10$ のときの出力を記せ（答えのみ）。

(2) $1\le n\le500$ のとき、どのような出力になるか理由とともに述べよ。

题目描述

考虑上面的 Pascal 程序。

(1) 输入 $10$ 时输出什么？只写答案。

(2) 输入任意 $1\le n\le500$ 时，会输出哪些整数对？说明理由。

Kai

(1)

1 1
6 6

(2)

出力は次の組を第 $1$ 成分の昇順に並べたものである。

• 常に $(1,1)$。
• $n$ 以下の完全数 $i$ に対する $(i,i)$。
• $i<j\le n$ を満たす友愛数の組 $(i,j)$。

実際、$i\ge2$ に対して、初期値の $1$ に加えて $2$ 以上の真の約数を一度ずつ加算するので、最初の二重ループ終了後には

$$a[i]=s(i):=\sum_{\substack{d\mid i\\1\le d<i}}d\quad(i\ge2),\qquad a[1]=1.$$

出力条件は $i\le a[i]\le n$ および $a[a[i]]=i$。$i=a[i]$ なら完全数、$i<a[i]$ なら友愛数の小さい方を先にした組であり、重複はない。$i=1$ は初期値によって特別に出力される。

この範囲の具体的な候補は $(1,1),(6,6),(28,28),(220,284),(496,496)$ であり、第 $2$ 成分が $n$ 以下のものが出力される。