【数论】GCD SUM（P2398）

ssllyf

已于 2022-02-16 16:59:58 修改

阅读量187

点赞数

分类专栏：数学&数论文章标签： luogu 数论

于 2021-11-04 07:24:23 首次发布

本文链接：https://blog.csdn.net/ssllyf/article/details/121134551

版权

数学&数论专栏收录该内容

28 篇文章

订阅专栏

正题

P2398

题目大意

给出n，求 $\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)$

解题思路

考虑先枚举gcd，那么有

$\sum_{d=1}^nd\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[gcd(i,j)=1]$

$\varphi(n)=\sum_{i=1}^n[gcd(i,n]=1]\\ \sum_{k=1}^n\varphi(k)=\sum_{i=1}^n\sum_{j=1}^i[gcd(i,j)=1]$

原式后面一段比上面多了 $j > i$ 的情况，这种情况的方案数和 $j\leq i$ 的方案数是相等的，可以直接乘2，不过要把 $\varphi(1)$ 重复计算的减去

那么原式为

$\sum_{d=1}^nd(2\times \sum_{i=1}^{n/d}\varphi(i)+1)$

后面一段可以用前缀和做，然后可以直接整除分块

时间复杂度 $O(\sqrt{n})$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
ll n,w,ans,p[N],phi[N],prime[N];
const ll MX=100000;
void work()
{
	phi[1]=1;
	for(ll i=2;i<=MX;++i){
		if(!p[i]){
			prime[++w]=i;
			phi[i]=i-1;
		}
		for(ll j=1;j<=w&&i*prime[j]<=MX;++j){
			p[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(ll i=2;i<=n;++i)
		phi[i]+=phi[i-1];
	return;
}
int main()
{
	scanf("%lld",&n);
	work();
	for(ll l=1,r=0;l<=n;l=r+1){
		r=n/(n/l);
		ans+=(phi[n/l]*2-1)*(r+l)*(r-l+1)/2;
	}
	printf("%lld",ans);
	return 0;
}