题目

分析

\[\large \begin{split} \sum_{i=1}^n\sum_{j=1}^n\varphi(\gcd(i,j)) &=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}\varphi(d)[\gcd(i,j)=1]\\ &=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[\gcd(i,j)=1]\\ &=\sum_{d=1}^n\varphi(d)\sum_{t=1}^{\lfloor\frac nd\rfloor}\mu(t)\lfloor\frac n{dt}\rfloor^2\\ &=\sum_{k=1}^n\lfloor\frac nk\rfloor^2\sum_{d\mid k}\varphi(d)\mu(\frac kd) \end{split} \]

容易发现后面的柿子是个卷积，两个都是积性函数，根据狄利克雷卷积的性质，整体也是积性函数，然后分析一下不难得出 \(f(1),f(p),f(p^k)\) 的值，于是可以线性筛，再做一下前缀和，前面的直接整除分块即可。

扩展：貌似还有其他做法，比如欧拉函数

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define inc(x,y,mod) (((x)+(y))>=(mod)?(x)+(y)-(mod):(x)+(y))
#define dec(x,y,mod) ((x)-(y)<0?(x)-(y)+(mod):(x)-(y))
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define dep(i,y,x) for(int i=(y);i>=(x);i--)
const int N=1e7+5,M=2e5+5,MOD=1e9+7;
int n,m,k,Ans;
int cnt,prime[N],f[N],low[N];
ll pre[N];//low指的是这个数对应最小质因子的最高次幂对应的值
bool vis[N];
inline void GetPrimes(int d){
	vis[1]=true;f[1]=low[1]=pre[1]=1;//对1进行定义 
	for(ll i=2;i<=d;i++){
		if(!vis[i]) prime[++cnt]=low[i]=i,f[i]=i-2;//对质数进行定义 
		pre[i]=pre[i-1]+f[i];
		for(ll j=1;j<=cnt&&i*prime[j]<=d;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0){
                low[i*prime[j]]=low[i]*prime[j];
                if (low[i]==i) f[i*prime[j]]=i*prime[j]-2*i+i/prime[j];//对质数的若干次幂进行定义(一般由f[i]递推);
                else f[i*prime[j]]=f[i/low[i]]*f[low[i]*prime[j]];//把当前质因子的所有项剃掉，然后把新的加回来
                break;
            }
            low[i*prime[j]]=prime[j];
			f[i*prime[j]]=f[i]*f[prime[j]];//通过 f(n),f(m) 计算 f(nm) 
		}
	}
	return ;
}
inline ll Calc(int x){
	ll res=0;
	for(int l=1,r;l<=x;l=r+1){
		r=x/(x/l);
		res+=1ll*(x/l)*(x/l)*(pre[r]-pre[l-1]);
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	GetPrimes(1e7);
	int t;cin>>t;
	while(t--){
		cin>>n;
		cout<<Calc(n)<<endl;
	}
	return 0;
}

BSOJ3348【BZOJ4804】欧拉心算

题目

分析

代码

推荐阅读