GCDSUM - Tổng các ước chung lớn nhất

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program GCDSUM;
Const
  input  = '';
  output = '';
  maxn = 1000000;
Var
  fi,fo: text;
  p,g: array [1..maxn] of integer;
  f: array [1..maxn] of int64;
  n: integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure primegens;
Var
  i,k: integer;
Begin
  Fillchar(p, sizeof(p), 0);
  For i:= 2 to maxn do if p[i] = 0 then
    Begin
      k:= 2 * i;
      While k <= maxn do
        Begin
          p[k]:= i;
          k:= k + i;
        End;
    End;
End;

Procedure gens;
Var
  i,tmp,pw: integer;
Begin
  g[1]:= 1;
  For i:= 2 to maxn do
    if p[i] = 0 then g[i]:= 2 * i - 1 else
      Begin
        tmp:= i;
        pw:= 0;

        While tmp mod p[i] = 0 do
          Begin
            tmp:= tmp div p[i];
            inc(pw);
          End;

        If tmp = 1 then g[i]:= (pw + 1) * i - pw * i div p[i] else g[i]:= g[tmp] * g[i div tmp];      
      End;

  f[1]:= 0;
  For i:= 2 to maxn do f[i]:= f[i - 1] + g[i] - i;  
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  primegens;
  gens;

  openfile;
  Repeat
    Readln(fi, n);
    If n <> 0 then writeln(fo, f[n]);
  Until n = 0;
  closefile;
End.

Download