原題：

http://172.16.0.132/senior/#contest/show/2058/0

題目描述：

小菜的妹妹小詩(shī)就要讀小學(xué)了！正所謂計(jì)算機(jī)要從娃娃抓起，小菜決定在幼兒園最后一段輕松的時(shí)間里教妹妹編程。
小菜剛教完gcd即最大公約數(shù)以后，一知半解的妹妹寫了如下一段代碼：
sum:=0;
for i:=1 to n-1 do
for j:=i+1 to n do sum:=sum+gcd(i,j)
顯然這個(gè)程序的效率是很低的，小明打算寫一個(gè)更強(qiáng)的程序，在求出sum的同時(shí)比妹妹跑的更快。

輸入：

第一行一個(gè)整數(shù)t，即表示有t組數(shù)據(jù)
接下來(lái)t行，每行一個(gè)整數(shù)n

輸出：

t行，每行一個(gè)整數(shù)，表示n所對(duì)應(yīng)的sum值

樣例輸入：

2
10
100

樣例輸出：

67
13015

分析：

以下分析借鑒于HownoneHe博客
首先假設(shè)我們要求i=1~n的gcd(n,i)的和
我們可以先假設(shè)gcd(n,i)=k,則gcd(n/k,i/k)=1
即假設(shè)gcd(n/k,x)=1 則gcd(n,x?k)=k
gcd(n,x?k)=k k的取值是確定的，即n的所有因子，
所以滿足gcd(n/k,x)=1中x的個(gè)數(shù)乘以k即為所有滿足gcd(n,i)=k的和。
因此就轉(zhuǎn)化為∑φ(n/k)?k

題目與這一假設(shè)很接近，只是將求i=1_{n的gcd(n,i)變成求i=1}(j=1~n)的gcd(i,j)
首先 我們可以設(shè)一個(gè)求和數(shù)組sum，他滿足
sum(n)=sum(n?1)+gcd(1,n)+gcd(2,n)+...+gcd(n?1,n)
設(shè) 數(shù)組f[i]表示j=1~i的gcd(j,i)值，則
f(n)=gcd(1,n)+gcd(2,n)+...+gcd(n?1,n)=∑i?φ(n/i)I是n的因子
我們可以先線性求phi，并保存
在預(yù)處理出sum和f數(shù)組，那么對(duì)于每個(gè)n，ans=sum[n]

實(shí)現(xiàn)：

var
        t,i,j,n,tot:longint;
        pri,p:array[0..1000001]of longint;
        f,sum:array[0..1000001]of int64;
        bz:array[0..1000001]of boolean;
procedure phi(m:longint);
var
        x:longint;
begin
        p[1]:=1;
        for i:=2 to m do
        begin
                if not bz[i] then
                begin
                        p[i]:=i-1;
                        inc(pri[0]);
                        pri[pri[0]]:=i;
                end;
                for j:=1 to pri[0] do
                begin
                        x:=pri[j];
                        if x*i>m then break;
                        bz[i*x]:=true;
                        if i mod x=0 then
                        begin
                                p[i*x]:=p[i]*x;
                                break;
                        end
                        else p[i*x]:=p[i]*p[x];
                end;
        end;
end;
begin
        readln(t);
        phi(1000000);
        for i:=1 to 1000000 do
        begin
                j:=2*i;
                while j<=1000000 do
                begin
                        f[j]:=f[j]+i*p[j div i];
                        j:=j+i;
                end;
        end;
        sum[1]:=0;
        for i:=2 to 1000000 do sum[i]:=sum[i-1]+f[i];
        while t>0 do
        begin
                readln(n);
                writeln(sum[n]);
                dec(t);
        end;
end.