千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2018年8月実施 専門 A5

标签：

• Programming-Basics

Author

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

Description

次の Pascal プログラムに正整数を入力する。

program sieve(input, output);
const maxind = 200;
var table: array[0..maxind] of boolean; n: integer;
function ti(n: integer): integer;
begin ti := (n div 7) * 2 + (n mod 7) div 5 end;
function fi(i: integer): integer;
begin
  if i mod 2 = 0 then fi := (i div 2) * 7 + 1
  else fi := (i div 2) * 7 + 6
end;
procedure mktab(maxnum: integer);
var n, m, d, dm, i: integer;
begin
  for i := 0 to maxind do table[i] := true;
  n := 6; d := 2;
  while n <= maxnum do begin
    if table[ti(n)] then begin
      m := n; dm := d;
      while m <= maxnum div n do begin
        table[ti(n*m)] := false; m := m+dm; dm := 7-dm
      end
    end;
    n := n+d; d := 7-d
  end
end;
begin
  readln(n);
  if (ti(n) <= maxind) and (n = fi(ti(n))) then begin
    mktab(n); writeln(n, table[ti(n)])
  end
end.

(1) $34$ を入力したときの出力を記せ（答のみ）。(2) 出力が存在する入力 $n$ の条件と、出力内容を理由付きで述べよ。

题目描述

向上述 Pascal 程序输入一个正整数。(1) 写出输入 $34$ 时的输出。(2) 给出产生输出的输入条件，并说明输出的布尔值表示什么及其理由。

Kai

(1) 34 TRUE（空白などの表示形式は処理系による）。

(2) 出力がある必要十分条件は

$$\boxed{1\le n\le701,\qquad n\equiv1\ \text{または}\ 6\pmod7}.$$

実際、fi は添字 $0,1,\ldots,200$ を $1,6,8,13,15,\ldots,701$ に対応させ、これらの値で ti が逆写像となる。

$S=\{m\ge1:m\equiv\pm1\pmod7\}$ とおく。出力は入力 $n$ と、次の真偽値である。

$$\boxed{\texttt{TRUE}\iff n=1\ \text{または}\ n\ne ab\ \text{となるすべての}\ a,b\in S\setminus\{1\}.}$$

つまり $S$ 内で二つの非単位元の積に分解できる場合だけ FALSE となる。

外側・内側のループは、それぞれ $S\setminus\{1\}$ とそのうち外側の値以上の数を昇順に走査し、積を消している。消される数は必ずこのような積である。逆に分解可能な $n$ について、$S$ 内の最小の非単位約数 $a$ をとると、$a$ は分解不能で、まだ消されていない。ある分解の小さい因子以下なので $a\le\sqrt n$、かつ $b=n/a\in S,b\ge a$ である。従って $a$ のループで $n$ は必ず消される。