lp3455 POI2007 ZAP-Queries

曾经有一道题，叫做YY的GCD，它求的是这样一个值：
$$\begin{equation}\begin{split}\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{p\in P}[gcd(x,y)==p] \end{split}\end{equation}$$
然后观察这道题的求和式：
$$\begin{equation}\begin{split}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==d] \end{split}\end{equation}$$
长得很像对不对？
事实上就是前者的简化版。
剩下的操作就很套路了。
$$\begin{equation}\begin{split}&\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(x,y)==1]\\=&\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k|gcd(x,y)}\mu(k)\\=&\sum_{x=1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{dk}\rfloor}\mu(k)\\=&\sum_{k=1}^{min(n,m)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor \end{split}\end{equation}$$
然后预处理出莫比乌斯函数跑数论分块即可。

#include<iostream>
#include<cstdio>

const int N = 100000+5;

int p[N/10],mu[N],n,m,d;
bool ip[N];
void prpr(){
	p[0]=0;mu[1]=1;ip[1]=1;
	for(int i=2;i<=100000;++i){
		if(!ip[i]){
			p[++p[0]]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=p[0]&&p[j]*i<=100000;++j){
			ip[i*p[j]]=1;
			if(!(i%p[j])){
				mu[i*p[j]]=0;
				break;
			}else{
				mu[i*p[j]]=-mu[i];
			}
		}
	}
	for(int i=2;i<=100000;++i){
		mu[i]+=mu[i-1]; 
	}
}
long long ans;
void init(){
	scanf("%d%d%d",&n,&m,&d);
	n>m?n^=m^=n^=m:0;
	ans=0;
	int k=0;
	for(int i=1;i<=n;i=k+1){
		k=std::min(n/(n/i),m/(m/i));
		ans+=1ll*(n/(i*d))*(m/(i*d))*(mu[k]-mu[i-1]);
	}
	printf("%lld\n",ans);
}

int main(){
	prpr();
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}