P2158 莫反做法

题目传送门。

题意：给定 \(n\)，求 \(2\cdot\Big(\sum\limits_{i=2}^{n-1}\varphi(i)\Big)+3\)。\(n\le4\times10^4\)。

一年前学习的做法是线性筛 \(O(n)\) 预处理 \(\varphi\)，然后按题意 \(O(n)\) 统计。今天颓废的时候突然发现这题还有莫反标签，于是用莫反做了一下。

把 \(\varphi\) 求和的式子变一下形：

\[\begin{align*} \sum\limits_{i=1}^n\varphi(i)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}[i\perp j]\\ &=\sum\limits_{j=1}^{i-1}\sum\limits_{j=1}^{i-1}[\gcd(i,j)=1]\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}\sum\limits_{d\mid \gcd(i,j)}\mu(d)\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}\sum\limits_{d\mid i,d\mid j}\mu(d)\\ &=\sum\limits_{d=1}^n\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}1\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor}1\\ &=\sum\limits_{d=1}^n\mu(d)\cdot\Big(\lfloor\frac{n}{d}\rfloor\Big)^2 \end{align*} \]

写的时候先用线性筛 \(O(n)\) 预处理出来 \(\mu\) 及其前缀和，然后上一个前缀和 + 数论分块就可以过了。注意代码中的式子和原本结论略有出入，但不影响。

预处理复杂度 \(O(n)\)，统计复杂度 \(O(\sqrt{n})\)。

代码：

#include<iostream>
#define int long long
using namespace std;

const int N=4e4+5;

int n;

namespace Math{
	
	int tot;
	
	int pri[N],mu[N],s_mu[N];
	bool flg[N];
	
	inline void init(int n){
		if(n==1){cout<<0<<"\n";exit(0);}
		mu[1]=1;
		for(int i=2;i<=n;++i){
			if(!flg[i])pri[++tot]=i,mu[i]=-1;
			for(int j=1;j<=tot&&i*pri[j]<=n;++j){
				flg[i*pri[j]]=1;
				if(!(i%pri[j])){mu[i*pri[j]]=0;break ;}
				mu[i*pri[j]]=mu[i]*(-1);
			}
		}
		for(int i=1;i<=n;++i)s_mu[i]=s_mu[i-1]+mu[i];
		return ;
	}
	
	inline int qry_s_mu(int l,int r){
		return s_mu[r]-s_mu[l-1];
	}
	
}using namespace Math;

signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;init(n);
	int res=0;
	int l=1,r=0;
	for(;l<=n-1&&r<=n-1;l=r+1){
		r=(n-1)/((n-1)/l);
		res+=qry_s_mu(l,r)*((n-1)/l)*((n-1)/l);
	}
	return cout<<res+2<<"\n",0;
}

提交记录。

发现一些莫反题的套路大概就是先找到形似 \([\gcd=1]\) 的式子，然后把那一个 \(\mu\) 的性质带进去算，然后把 \(d\) 放到前面枚举，然后整理成下取整 + 函数和的形式。