HDU - 1695 GCD (容斥原理)

http://acm.hdu.edu.cn/showproblem.php?pid=1695

題目大意：

給你 a b c d k

讓你從 (a,b)中選一個x (c,d) 中選一個y 保證 gcd(x,y) =k

并且 (3,5) (5,3) 視為一種選擇。

問：有多少種選擇

解題思路：

gcd(x,y) = k 那我們可以讓b和d同時/k

就可以化簡為 求(1,b) (1,d)中互質的數的個數。

就可以用這個題的思路：HDU - 4135 Co-prime

https://blog.csdn.net/weixin_43179892/article/details/98237974

這裡還有一個問題 就是重複的問題。怎麼去重呢？

看第一個樣例。 我們 i 周遊(1,3) 求 i 與（1，5）中互質的個數。那麼（1.3）中互質的數的個數就多加了一遍，是以我們減去一半（1-3）中和（1-3）中互質的對數一半 就是答案。

注意：k==0時直接輸出0 因為沒有數的gcd == 0

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> 
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 1e5+10;
int p[maxn];
int num = 0;
ll gcd(ll a,ll b){
	if(b==0) return a;
	else{
		return gcd(b,a%b);
	}
}
ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}
//對k分解質因數
void pr(int k){
	num = 0;
	for(int i=2;i*i<=k;i++){
		if(k%i==0){
			p[num++] = i;
			while(k%i==0){
				k/=i;
			}
		}
	}
	if(k>1) p[num++] = k;
}
ll ans = 0;
/// 1-N 中有多少和k不互質的
void dfs(int th,int time,ll now,ll N){
	if(time>num) return;
	ll lcc = lcm(now,p[th]);
	if(time&1) ans+=(N/lcc);
	else ans -= (N/lcc);
	for(int i=th+1;i<num;i++){
		dfs(i,time+1,lcc,N);
	}
}
///1-n中和k互質的數的個數
ll solve(ll k,ll n){
	pr(k);
	ans = 0;
	for(int i=0;i<num;i++){
		dfs(i,1,p[i],n);
	}
	return n-ans;
}
int main(){
	int cas = 1;
	int t;
	cin>>t;
	ll a,b,c,d,k;
	while(t--){
		scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
		if(k==0||k>b||k>d){
			printf("Case %d: 0\n",cas++);
			continue;
		}
		b/=k;
		d/=k;
		ll res = 0;
		for(ll i=1;i<=b;i++){
			res += solve(i,d);
		}
		int mm = min(b,d);
		ll ss = 0;
		for(int i=1;i<=mm;i++){
			ss += solve(i,mm);
		}	
		res = res - ss/2;
		printf("Case %d: %lld\n",cas++,res);
	}
	return 0;
}