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.