[济南集训 2017] 求gcd之和

题目大意:

求\(\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\)

解题报告:

有一个结论:一个数的所有因子的欧拉函数之和等于这个数本身

运用这个我们可以开始推:

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

\(\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\phi(d)\)

\(\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,j}\phi(d)\)

\(\sum_{d=1}^n\phi(d)*(n/d)*(m/d)\)

对于最后一个式子可以数论分块解决,但此题中不需要

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=1e7+5,mod=998244353;

typedef long long ll;

bool vis[N];int prime[N],num=0,n,m;ll sum[N],phi[N];

void solve(){

	int to;

	phi[1]=1;

	for(int i=2;i<=n;i++){

		if(!vis[i]){

			prime[++num]=i;

			phi[i]=i-1;

		}

		for(int j=1;j<=num && prime[j]*i<=n;j++){

			to=i*prime[j];vis[to]=true;

			if(i%prime[j])phi[to]=phi[i]*(prime[j]-1)%mod;

			else{

				phi[to]=phi[i]*prime[j]%mod;

				break;

			}

		}

	}

	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+phi[i],sum[i]%=mod;

}

void work()

{

	cin>>n>>m;

	if(n>m)swap(n,m);

	solve();

	ll ans=0;

	RG int j;

	for(RG int i=1;i<=n;i=j+1){

		j=Min(n/(n/i),m/(m/i));

		ans+=((sum[j]-sum[i-1])%mod+mod)%mod*(n/i)%mod*(m/i)%mod;

		if(ans>=mod)ans-=mod;

	}

	printf("%lld\n",ans);

}

int main()

{

	freopen("hoip.in","r",stdin);

	freopen("hoip.out","w",stdout);

	work();

	return 0;

}

巴特西

[济南集训 2017] 求gcd之和

最新文章

热门文章