51Nod-1188 最大公约数之和V2(欧拉函数)

$Description$
$Calculate \quad \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}gcd(i,j)$

$Solution$
对这个式子先考虑枚举 $j$ , $\sum_{j=2}^{n}$ , $i$ 就变为 $\sum_{i=1}^{j-1}$
$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}gcd(i,j)=\sum_{j=2}^{n}\sum_{i=1}^{j-1}gcd(i,j)=\sum_{i=1}^{n}\sum_{d|i}d\cdot \varphi(\frac{i}{d})-\frac{n\cdot (n+1)}{2}$
$\sum_{d|i}d\cdot \varphi(\frac{i}{d})$ 埃式筛法即可.

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define IN freopen("in.txt","r",stdin);
#define STR clock_t startTime = clock();
#define END clock_t endTime = clock();cout << double(endTime - startTime) / CLOCKS_PER_SEC *1000<< "ms" << endl;
const int N=5e6+6;
const int mod=1e9+7;
const int inv2=mod+1>>1;
typedef long long ll;
int prime[N],tot=0;
bool vis[N]={0};
ll f[N],phi[N];
void pre(){
    phi[1]=1;f[0]=phi[0]=0;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<N;i++)
    for(int j=i;j<N;j+=i)
    f[j]+=1LL*i*phi[j/i];
    for(int i=1;i<N;i++)f[i]+=f[i-1];
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%lld\n",f[n]-1ll*n*(n+1)/2);
    }
}