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;
}
0 条评论