2818: Gcd

 1 /**************************************************************
 2     Problem: 2818
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:1900 ms
 7     Memory:156476 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;ans:int64;
12    a,b:array[0..10000005] of longint;
13    c:array[0..10000005] of int64;
14 procedure phi;
15           var i,j:longint;
16           begin
17                m:=0;a[1]:=1;
18                for i:=2 to n do
19                    begin
20                         if a[i]=0 then
21                            begin
22                                 inc(m);
23                                 b[m]:=i;
24                                 a[i]:=i-1;
25                            end;
26                         for j:=1 to m do
27                             begin
28                                  if (i*b[j])>n then break;
29                                  if (i mod b[j])=0 then
30                                     a[i*b[j]]:=a[i]*b[j]
31                                  else
32                                      a[i*b[j]]:=a[i]*(b[j]-1);
33                             end
34                    end;
35           end;
36 begin
37      readln(n);m:=0;phi;ans:=0;
38      for i:=1 to n do c[i]:=c[i-1]+int64(a[i]);
39      for i:=1 to m do inc(ans,c[n div b[i]]*2-1);
40      writeln(ans);
41      readln;
42 end.