HDU1695(莫比乌斯反演+容斥)

题目链接

HDU1695

思路

先考虑简单的从1开始的

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==k]\\ &=\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[gcd(i,j)==1]\\ &= \sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}\sum_{d|gcd(i,j)}\mu(d)\\ 日常枚举d\\ &=\sum_{i=1}^{\frac{n}{k}}\mu(i)\frac{n}{ki}\frac{m}{ki}\\ \end{aligned}$$

这样我们就能O(n)求出1-N,1-M的，然后考虑a-b,c-d的，首先若从(1-b)(1-d)的话回多出两部分呢，一部分是前面的(1-(a-1))(1-d),以及后面的(1-b)(1-(c-1))但是这样就会重复计算了(1-(a-1))(1-(c-1))加上这部分即可，然后还有不能算重复的，其实就是找到他们交集的答案，然后除2即可.

代码示例

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e5+10;
int prime[N],cnt,mu[N];
bool vis[N];
int k;
void init(){
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])prime[cnt++]=i,mu[i]=-1;
		for(int j=0;j<cnt&&i*prime[j]<N;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
}
ll get(int a,int b){
	ll ans = 0;
	if(a>b)swap(a,b);
	if(a==0)return 0;
	for(int i=1;i<=a/k;i++){
		ans+=1ll*(b/(k*i))*(a/(k*i))*mu[i];
	}
	return ans;
}
int main(){
	int t;
	scanf("%d",&t);
	init();
	for(int cas=1;cas<=t;cas++)
	{
		int a,b,c,d;
		scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
		if(k==0) {
		printf("Case %d: %lld\n",cas,0ll);
		continue;
		}
		ll ax=max(a,c);
		ll am=min(b,d);
		ll ans = get(b,d);
		ll ans1 = get(a-1,d);
		ll ans2 = get(b,c-1);
		ll ans3 = get(a-1,c-1);
		ll ans4 =(get(am,am)+get(ax-1,ax-1))/2;
		printf("Case %d: %lld\n",cas,ans-ans1-ans2+ans3-ans4);
	}
}