记录编号	85864	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	C语言入门	是否通过	通过
代码语言	Pascal	运行时间	9.584 s
提交时间	2014-01-14 18:46:42	内存使用	91.72 MiB

program o;
var
f,d,g:array [0..4000000] of int64;
i,j:longint;
k,n,ans:int64;
begin
assign (input,'gcd_extreme.in');
assign (output,'gcd_extreme.out');
reset (input);
rewrite (output);
 for i:=1 to 4000000 do
  begin
   f[i]:=i;
   g[i]:=i+g[i-1];
  end;
 f[1]:=0;
 k:=0;
 for i:=2 to 4000000 do
  begin
   if f[i]=i then
    begin
     for j:=2 to (4000000 div i) do
      f[j*i]:=f[j*i]*(i-1)div i;
     f[i]:=i-1;
    end;
  end;
 for i:=2 to 4000000 do
  f[i]:=f[i]+f[i-1];
  n:=1;
while n<>0 do
 begin
  read (n);
  ans:=0;
  if n<>0 then
   begin
    i:=1;
    while i<=n do
     begin
      j:=n div i;
      ans:=ans+f[j]*(g[n div j]-g[i-1]);
      i:=n div j+1;
     end;
    writeln (ans);
   end;
 end;
close (input);
close (output);
end.