P1390 公约数的和

题目描述

给定 n，求

\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)

其中 \gcd(i, j) 表示 i 和 j 的最大公约数。

2\leq n \leq 2\times10^6

Solution

\sum_{p=1}^np\times\sum_{i = 1}^n \sum_{j = i + 1}^n [\gcd(i, j)=p]

于是有
\sum_{p=1}^np\times\sum_{i=1}^n\sum_{j=1}^{i-1}[\gcd(i, j)=p]

\sum_{p=1}^np\times\sum_{i=1}^n\sum_{j=1}^{\frac{i-1}{p}}[\gcd(\frac{i}{p}, j)=1]

于是有
\sum_{p=1}^np\times\sum_{i=1}^{\frac{n}{p}}\phi(i)
最后减去 \sum_{i-1}^ngcd(x,x)

#include<bits/stdc++.h>
using namespace std;

const int N =2e6+10;
int vis[N];   //记录是否被筛；或者用于记录最小质因子
int prime[N]; //记录质数
int phi[N];   //记录欧拉函数
long long sum[N];   //计算欧拉函数的和
int euler(int n)  {  
    int ans=n;  
    for(int i=2;i*i<=n;i++){  
        if(n%i==0){  
            ans-=ans/i;  
            while(n%i==0){  
                n/=i;  
            }  
        }  
    }  
    if(n>1)ans-=ans/n;  
    return ans;  
}
void get_phi(){  //模板：求1～maxn范围内的欧拉函数
    phi[1]=1;
    int cnt=0;
    for(int i=2;i<N;i++) {
        if(!vis[i]) {
            vis[i]=i; //vis[i]=1; //二选一：前者记录最小质因子，后者记录是否被筛
            prime[cnt++]=i;       //记录质数
            phi[i]=i-1;           //情况（1）：i是质数，它欧拉函数值=i-1
        }
        for(int j=0;j<cnt;j++) {
            if(i*prime[j] > N)  break;
            vis[i*prime[j]] = prime[j]; //vis[i*prime[j]]=1; 
                                 //二选一：前者记录最小质因子，后者记录是否被筛
            if(i%prime[j]==0){          //看OI WIKI
                phi[i*prime[j]] = phi[i]*prime[j];
                                 //情况（2）：i是prime[j]的k次方
                break;
            }
            phi[i*prime[j]] = phi[i]*phi[prime[j]];  
                                //情况（3）：i和prime[j]互质，递推出i*prime[j]
        }
    }
}

int main(){
    get_phi();        //计算所有的欧拉函数
    long long ans =0 ;
    for(int i=1;i<N;++i)
        sum[i] = sum[i-1]+phi[i];
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int p = n/i;
        ans += 1ll*i*sum[p];
    }
    ans -= 1ll*n*(n+1)/2;
    cout<<ans;
    return 0;
}