\[\begin{eqnarray*}
ans&=&\sum_{i=1}^nf(i)\\
&=&\sum_{i=1}^n\sum_{d|i}\gcd(d,\frac{i}{d})\\
&=&\sum_{i=1}^n\sum_{d|i}\sum_{k|d,k|\frac{i}{d}}\varphi(k)\\
&=&\sum_{k=1}^n\varphi(k)\sum_{k^2|i}\sigma_0(\frac{i}{k^2})\\
&=&\sum_{k=1}^n\varphi(k)\sum_{i=1}^{\lfloor\frac{n}{k^2}\rfloor}\lfloor\frac{n}{i}\rfloor\\
&=&\sum_{k=1}^{\sqrt{n}}\varphi(k)S(\lfloor\frac{n}{k^2}\rfloor)
\end{eqnarray*}\]

其中

\[S(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\]

枚举所有$k$，然后分段计算$S$即可。

时间复杂度

\[\begin{eqnarray*}
T(n)&=&O(\sqrt{n}+\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i^2}})\\
&=&O(\sqrt{n}\sum_{i=1}^{\sqrt{n}}\frac{1}{i})\\
&=&O(\sqrt{n}\log n)
\end{eqnarray*}\]

#include<cstdio>typedef long long ll;const int N=31622800;const ll n=1000000000000000LL;int i,j,k,tot,p[N/10],phi[N];bool v[N];ll ans;inline ll F(ll n){  ll ret=0;  for(ll i=1,j;i<=n;i=j+1){    j=n/(n/i);    ret+=n/i*(j-i+1);  }  return ret;}int main(){  for(phi[1]=1,i=2;i<=n/i;i++){    if(!v[i])phi[i]=i-1,p[tot++]=i;    for(j=0;j<tot;j++){      k=i*p[j];      if(k>n/k)break;      v[k]=1;      if(i%p[j])phi[k]=phi[i]*(p[j]-1);else{        phi[k]=phi[i]*p[j];        break;      }    }  }  for(i=1;i<=n/i;i++)ans+=F(n/i/i)*phi[i];  return printf("%lld",ans),0;}

PE530 : GCD of Divisors