原題：

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

題目描述：

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

輸入：

第一行一個整數(shù)t痹雅，即表示有t組數(shù)據
接下來t行，每行一個整數(shù)n

輸出：

t行糊识，每行一個整數(shù)绩社，表示n所對應的sum值

樣例輸入：

2
10
100

樣例輸出：

67
13015

分析：

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

題目與這一假設很接近，只是將求i=1_{n的gcd(n,i)變成求i=1}(j=1~n)的gcd(i,j)
首先 我們可以設一個求和數(shù)組sum拌滋，他滿足
sum(n)=sum(n?1)+gcd(1,n)+gcd(2,n)+...+gcd(n?1,n)
設 數(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，并保存
在預處理出sum和f數(shù)組败砂，那么對于每個n赌渣，ans=sum[n]

實現(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.