luogu P2398 GCD SUM |欧拉函数

题目描述

求

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

输入格式

第一行一个整数 (n)。

输出格式

第一行一个整数表示答案。

---

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e5+5,mod=1e9+7;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') {
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int phi[N];
void pre(int n){
	for(int i=1;i<=n;i++)phi[i]=i;
	for(int i=2;i<=n;i++)
	if(phi[i]==i)
	for(int j=i;j<=n;j+=i)phi[j]=phi[j]/i*(i-1);
	for(int i=1;i<=n;i++)phi[i]+=phi[i-1];
}
int sum(int n){
	return phi[n]*2-1;
}
signed main(){
	pre(1e5);
	int n=read();
	int ans=0;
	for(int d=1,nd=0;d<=n;d=nd+1){
		nd=n/(n/d);
		ans+=((d+nd)*(nd-d+1)>>1)*sum(n/d);
	}
	cout<<ans<<endl;
}