VII.[NOI2016] 循环之美

依据小学数论知识，我们要求

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] \]

因为后面的 \(k\) 是个常数，所以我们就想把它搞出来。

\[\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\Big[\gcd(i,j)=1\Big]\Big[\gcd(j,k)=1\Big]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\Big[\gcd(i,j)=1\Big]\sum\limits_{d|j,d|k}\mu(d)\\=&\sum\limits_{d|k}\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^{m/d}\Big[\gcd(i,jd)=1\Big]\\=&\sum\limits_{d|k}\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^{m/d}\Big[\gcd(i,j)=1\Big]\Big[\gcd(i,d)=1\Big]\end{aligned} \]

推到这步时，我们发现它好像跟我们最开头的式子莫名相似。

因此我们设原式为 \(f(n,m,k)\)，则我们这里后面的式子好像就是 \(f(m/d,n,d)\)。

因为每次都会除掉一个 \(d\)，而 \(n\) 和 \(m\) 是轮流颠倒着除的，所以复杂度应该有个 \(\log m\log n\)。又因为我们要暴力枚举 \(k\) 的所有因数，所以又乘上一个 \(\sqrt k\)。跑到 \(k=1\) 的层之后又要求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor\)，因此还要上杜教筛。

但实际上，这个算法复杂度不是很优，2s内卡过不去，权当参考。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20000000;
int pri[20010000],mu[20010000];
void sieve(){
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!pri[i])pri[++pri[0]]=i,mu[i]=-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
			pri[i*pri[j]]=true;
			if(i%pri[j])mu[i*pri[j]]=-mu[i];
			else break;
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
unordered_map<int,int>mp;
int MU(int n){
	if(n<=N)return mu[n];
	if(mp.find(n)!=mp.end())return mp[n];
	int ret=1;
	for(int l=2,r;l<=n;l=r+1)r=n/(n/l),ret-=(r-l+1)*MU(n/l);
	return mp[n]=ret;
}
ll func(int n,int m,int k){
	if(!n||!m)return 0;
	if(k==1){
		ll ret=0;
		for(int l=1,r;l<=min(n,m);l=r+1)r=min(n/(n/l),m/(m/l)),ret+=1ll*(n/l)*(m/l)*(MU(r)-MU(l-1));
		return ret;
	}
	ll ret=0;
	for(int d=1;d*d<=k;d++){
		if(k%d)continue;
		ret+=func(m/d,n,d)*(mu[d]-mu[d-1]);
		if(d*d!=k)ret+=func(m/(k/d),n,k/d)*(mu[k/d]-mu[k/d-1]);
	}
	return ret;
}
int n,m,k;
int main(){
	sieve();
	scanf("%d%d%d",&n,&m,&k);
	printf("%lld\n",func(n,m,k));
	return 0;
}

接下来我们反其道而行之，保留 \(k\)，处理 \(i\)。

\[\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\Big[\gcd(i,j)=1\Big]\Big[\gcd(j,k)=1\Big]\\=&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d|i,d|j}\mu(d)\Big[\gcd(j,k)=1\Big]\\=&\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\sum\limits_{j=1,d|j}^m\Big[\gcd(j,k)=1\Big]\\=&\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\sum\limits_{j=1}^{m/d}\Big[\gcd(jd,k)=1\Big]\\=&\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\Big[\gcd(d,k)=1\Big]\sum\limits_{j=1}^{m/d}\Big[\gcd(j,k)=1\Big]\end{aligned} \]

我们令 \(f(n)\) 表示 \(\sum\limits_{j=1}^n\Big[\gcd(j,k)=1\Big]\)。当 \(j\leq k\) 时，可以预处理；当 \(j>k\) 时，每 \(k\) 位一个循环节，且循环节内部大小为 \(\varphi(k)\)。

于是有式子

\[f(n)=\left\lfloor\dfrac{n}{k}\right\rfloor\varphi(k)+f(n\bmod k) \]

则现在 \(f\) 即可 \(O(1)\) 计算。我们即可将原式改写为 \(\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\Big[\gcd(d,k)=1\Big]f\Big(\left\lfloor m/d\right\rfloor\Big)\)。

\[\begin{aligned}&\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\Big[\gcd(d,k)=1\Big]f\Big(\left\lfloor m/d\right\rfloor\Big)\\=&\sum\limits_{d=1}^{\min(n,m)}\left\lfloor\dfrac{n}{d}\right\rfloor f\Big(\left\lfloor m/d\right\rfloor\Big)\mu(d)\sum\limits_{p|d,p|k}\mu(p)\\=&\sum\limits_{p|k}\mu(p)\sum\limits_{d=1,p|d}^{\min(n,m)}\left\lfloor\dfrac{n}{d}\right\rfloor f\Big(\left\lfloor m/d\right\rfloor\Big)\mu(d)\\=&\sum\limits_{p|k}\mu(p)\sum\limits_{d=1}^{\min(n,m)/p}\left\lfloor\dfrac{n}{dp}\right\rfloor f\Big(\left\lfloor m/dp\right\rfloor\Big)\mu(dp)\end{aligned} \]

因为 \(\mu\) 是积性函数，且有平方项的数的 \(\mu\) 值为 \(0\)，故 \(\mu(dp)=\mu(d)\mu(p)\Big[\gcd(d,p)=1\Big]\)，于是上式改写成 \(\sum\limits_{p|k}\mu(p)\sum\limits_{d=1}^{\min(n,m)/p}\left\lfloor\dfrac{n}{dp}\right\rfloor f\Big(\left\lfloor m/dp\right\rfloor\Big)\mu(d)\mu(p)\Big[\gcd(d,p)=1\Big]\)。

\[\begin{aligned}&\sum\limits_{p|k}\mu(p)\sum\limits_{d=1}^{\min(n,m)/p}\left\lfloor\dfrac{n}{dp}\right\rfloor f\Big(\left\lfloor m/dp\right\rfloor\Big)\mu(d)\mu(p)\Big[\gcd(d,p)=1\Big]\\=&\sum\limits_{p|k}\mu^2(p)\sum\limits_{d=1}^{\min(n,m)/p}\left\lfloor\dfrac{n}{dp}\right\rfloor f\Big(\left\lfloor m/dp\right\rfloor\Big)\mu(d)\Big[\gcd(d,p)=1\Big]\\=&\sum\limits_{p|k}\mu^2(p)\sum\limits_{d=1}^{\min(n,m)/p}\left\lfloor\dfrac{n/p}{d}\right\rfloor f\Big(\left\lfloor \dfrac{m/p}{d}\right\rfloor\Big)\mu(d)\Big[\gcd(d,p)=1\Big]\end{aligned} \]

发现了什么？后面一大坨跟我们开始的式子 \(\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\Big[\gcd(d,k)=1\Big]f\Big(\left\lfloor m/d\right\rfloor\Big)\) 极度相似。于是我们设 \(g(n,m,k)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\Big[\gcd(d,k)=1\Big]f\Big(\left\lfloor m/d\right\rfloor\Big)\)，则将最后的式子代进去，发现就是

\[\sum\limits_{p|k}\mu^2(p)g\Big(\dfrac{n}{p},\dfrac{m}{p},p\Big) \]

边界就是到 \(k=1\) 时，有 \(g(n,m,1)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor f\Big(\left\lfloor m/d\right\rfloor\Big)\)。\(\mu\) 上杜教筛处理，剩下两个可以简单整除分块。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20000000;
int pri[20010000],mu[20010000];
void sieve(){
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!pri[i])pri[++pri[0]]=i,mu[i]=-1;
		for(int j=1;j<=pri[0]&&i*pri[j]<=N;j++){
			pri[i*pri[j]]=true;
			if(i%pri[j])mu[i*pri[j]]=-mu[i];
			else break;
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
unordered_map<int,int>mp;
int MU(int n){
	if(n<=N)return mu[n];
	if(mp.find(n)!=mp.end())return mp[n];
	int ret=1;
	for(int l=2,r;l<=n;l=r+1)r=n/(n/l),ret-=(r-l+1)*MU(n/l);
	return mp[n]=ret;
}
int F(int n); 
ll func(int n,int m,int k){
	if(!n||!m)return 0;
	if(k==1){
		ll ret=0;
		for(int l=1,r;l<=min(n,m);l=r+1)r=min(n/(n/l),m/(m/l)),ret+=1ll*(n/l)*F(m/l)*(MU(r)-MU(l-1));
		return ret;
	}
	ll ret=0;
	for(int d=1;d*d<=k;d++){
		if(k%d)continue;
		if(mu[d]!=mu[d-1])ret+=func(n/d,m/d,d);
		if(d*d!=k&&mu[k/d]!=mu[k/d-1])ret+=func(n/(k/d),m/(k/d),k/d);
	}
	return ret;
}
int k,f[2010];
int F(int n){return (n/k)*f[k]+f[n%k];}
int n,m;
int main(){
	sieve();
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++)f[i]=f[i-1]+(__gcd(i,k)==1);
	printf("%lld\n",func(n,m,k));
	return 0;
}

本题是道难得的莫反好题，有多种思路，其中有三点我认为最为精妙：一是 \([\gcd(i,j)=1][\gcd(j,k)=1]\Leftrightarrow[\gcd(j,ik)=1]\)，二是 \(\mu(dp)=\mu(d)\mu(p)[\gcd(d,p)=1]\)，这两点在乘积项和项的乘积间架起了桥梁；还有一点就是函数式思考，遇见形式相似的东西就尝试设函数递归处理，在某些时候不失为一种手段。