莫反做题记

$\quad $ 一些（两个）常用结论：

$\quad $ 反演公式:

给定函数 \(f(x)\) ，定义函数 \(g(n) ={\sum_{d|n}}{f(d)}\)

则有：

[POI2007] ZAP-Queries

即：
\begin{aligned}
ans&=\sum _{i=1}^{n}{\sum _{j=1}^{m}{[gcd(i,j)=d]}}\\
&=\sum _{i=1}^{\lfloor{\frac{n}{d}\rfloor}}{\sum _{j=1}^{\lfloor{\frac{m}{d}}\rfloor}{[gcd(i,j)=1]}}\\
&=\sum _{i=1}^{\lfloor{\frac{n}{d}\rfloor}}{\sum _{j=1}^{\lfloor{\frac{m}{d}}\rfloor}{\sum _{k|gcd(i,j)}{\mu(k)}}}\\
&=\sum _{k=1}^{\lfloor{\frac{n}{d} \rfloor}}{\mu(k)\sum _{i=1}^{\lfloor{\frac{n}{d}}\rfloor}}\sum _{j=1}^{\lfloor{\frac{m}{d} \rfloor} }{[k|i][k|j]}\\
&=\sum _{k=1}^{\lfloor {\frac{n}{d}} \rfloor}{\mu(k){\lfloor{\frac{n}{kd}\rfloor}{\lfloor{\frac{m}{kd}}\rfloor}}}
\end{aligned}

$\quad $ 然后再除法分块即可。

#define yhl 0
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+100;
int miu[N],prime[N],tot,t,n,m,d;
bool vis[N];
void get_miu(){
	miu[1]=1;vis[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])prime[++tot]=i,miu[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j])miu[i*prime[j]]=-miu[i];
			else{
				miu[i*prime[j]]=yhl;break;
			}
		}
	}
	for(int i=1;i<N;i++)miu[i]+=miu[i-1];
}
int ghfz(int n,int m){
	int ans=yhl,r=yhl;
	for(int i=1;i<=n;i=r+1){
		r=min(n/(n/i),m/(m/i));
		ans+=(miu[r]-miu[i-1])*(n/i)*(m/i);
	}
	return ans;
}
int main(){
	get_miu();
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&m,&d);
		n/=d,m/=d;if(m<n)swap(n,m);
		printf("%d\n",ghfz(n,m));
	}
	return yhl;
}

$\quad $ \(三倍经验\) 双亲数 [HAOI2011] Problem b，后面这个拿容斥搞一下即可。

YY的GCD

\begin{aligned}
ans&=\sum _{i=1}^{n}{\sum _{j=1}^{m}{[gcd(i,j)=p,p\in prime]}}\\
&=\sum _{p \in prime }{\sum _{i=1}^{n}{\sum _{j=1}^{m}{[gcd(i,j)}=p]}}\\
&=\sum _{p \in prime}{\sum _{i=1}^{\lfloor {\frac{n}{p}} \rfloor}}{\sum _{j=1}^{\lfloor {\frac{m}{p}}\rfloor}}{[gcd(i,j)=1]}\\
&=\sum _{p \in prime}{\sum _{i=1}^{\lfloor {\frac{p}{p}}\rfloor}}{\sum _{j=1}^{\lfloor {\frac{m}{p}} \rfloor}}{\sum _{k|gcd(i,j}}{\mu (k)}\\
&=\sum _{p \in prime}{\sum _{k=1}^{\lfloor {\frac{n}{p}} \rfloor}}{\mu(k)}{\sum _{i=1}^{\lfloor {\frac{n}{p}}{\rfloor}}}{[k|i]}{\sum _{j=1}^{\lfloor {\frac{m}{p}\rfloor}}}{[k|j]}\\
&=\sum _{p \in prime}{\sum _{k=1}^{\lfloor {\frac{n}{p}}\rfloor}}{\mu(k)\lfloor {\frac{n}{pk}} \rfloor}{\lfloor {\frac{m}{pk}} \rfloor}
\end{aligned}

$\quad $ 令 \(T=pk\) ，再变为枚举 \(T\) 则：

\begin{aligned}
ans&=\sum _{T=1}^{n}{\lfloor {\frac{n}{T}} \rfloor \lfloor{\frac{m}{T}\rfloor}}{\sum _{k|T,k\in prime}}{\mu(\frac{T}{k})}
\end{aligned}
$\quad $ 后面部分预处理出来，然后拿前缀和维护一下即可，再用根号分治就好了。

#define yhl 0
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+100;
int miu[N],prime[N],tot,t,n,m,d,f[N],s[N];
bool vis[N];
void get_miu(){
	miu[1]=1;vis[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])prime[++tot]=i,miu[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j])miu[i*prime[j]]=-miu[i];
			else{miu[i*prime[j]]=yhl;break;}
		}
	}
	for(int i=1;i<=tot;i++)
		for(int j=1;j*prime[i]<N;j++)
			f[j*prime[i]]+=miu[j];
	for(int i=1;i<N;i++)s[i]=s[i-1]+f[i];
}
int ghfz(int n,int m){
	int ans=yhl,r=yhl;
	for(int i=1;i<=n;i=r+1){
		r=min(n/(n/i),m/(m/i));
		ans+=(s[r]-s[i-1])*(n/i)*(m/i);
	}
	return ans;
}
signed main(){
	get_miu();
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		if(m<n)swap(n,m);
		printf("%lld\n",ghfz(n,m));
	}
	return yhl;
}

[SDOI2015] 约数个数和

$\quad $ 即 \(ans=\sum _{i=1}^{n}{\sum _{j=1}^{m}{d(ij)}}\) ，其中 \(d(x)\) 为 \(x\) 的约数个数。

$\quad $ 一个结论：\(d(ij)=\sum _{a|i}{}\sum _{b|j}{[gcd(a,b)=1]}\) ，证明我也不知道