......
数论题目可能的坑数据:
大素数 HCN SquareFree 只有一个素因子的数 
只有2个素因子且2个素因子次数都为1的数

F(x)积性证明
首先有几个公式 
    Sigma(d|n,phi(d))=n
    g(x)=Sigma(d|n,f(d)) f(x)积性函数->g(x)积性函数
    积性函数的积仍然是积性函数

然后
原式=Sigma Sigma(d|gcd(i,n),phi(d))
    =Sigma Sigma(d|i,d|n,phi(d))
    =Sigma(d|n,phi(d)*(n/d))
d|n时n/d也是积性函数

结合前面的公式,f(x)积性函数

function ans(n:int64):int64;
var i,j,k:int64;
begin
ans:=1; i:=2;
while (i<=trunc(sqrt(n)))and(n<>1) do begin
        j:=trunc(sqrt(n));
        while (i<=j)and(n mod i<>0) do inc(i);
        if i>j then break;
        k:=i<<1-1; n:=n div i; j:=i;
        while n mod i=0 do begin
                k:=(k*i+j*i-j);
                j:=j*i;
                n:=n div i;
        end;
        ans:=ans*k;
end;
if n<>1 then
        ans:=ans*(n<<1-1);
end;