HDU 1695 GCD(歐拉函數＋容斥原理)

求[1..b]中的x和[1..d]中的y有多少gcd(x,y) = k.

要求gcd(x,y) = k，則等價於求 gcd(x/k,y/k) = 1.所以問題轉化成求[1..b/k]和[1..d/k]中有多少對gcd(x,y) = 1.

進一步轉換成 枚舉[1,d]區間裡的n與][1, b]的區間的數互質的個數,這裡d>=b.

因為[1,b]包含在[1,d]裡,所以[1,b]相當於累加歐拉函數phi(i)的值,而[b + 1, d]這個區間可以通過容斥原理來求出.

要求n與][1, b]的區間的數互質的個數,可以考慮求與n不互質數的個數v, 那麼互質的數自然就是b - v.

所以分解n的素因子,考慮n的素因子pi,則[1, b]中與pi不互質的數的個數是[b/pi](即其multiples).

如果這樣累加[b/pi]的話則會加上很多重復的值(一個數可能有多個素因子),這裡容斥原理就派上用場了.

10W內的數素因子並不多,可以通過枚舉2^m的組合來求,m為素因子個數.

#include 
#include 
#include 
using namespace std;
const int MAX = 100010;
vector pf[MAX];
long long phi[MAX];

void init_phi(){
	for(int i = 0; i < MAX; ++i)phi[i] = 0;
	phi[1] = 1;
	for(int i = 2; i < MAX; ++i){
		if(!phi[i]){
			for(int j = i; j < MAX; j += i){
				if(!phi[j])phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
				if(j != i)
					pf[j].push_back(i);
			}
		}
	}
	for(int i = 1; i < MAX; ++i){
		phi[i] = phi[i] + phi[i - 1];
	}
}

long long inclusion_exclusion(long long r, long long n){
	long long ret = 0;
	for(int i = 1; i < (1 << pf[n].size()); ++i){
		int bits = 0, multiple = 1;
		for(int j = 0; j < pf[n].size(); ++j){
			if(i & (1 << j)){
				bits++;
				multiple *= pf[n][j];
			}
		}
		if(bits & 1)ret += r / multiple;
		else ret -= r / multiple;
	}
	return r - ret;
}

int main(){
	init_phi();
	int T, caseno = 1;
	scanf("%d", &T);
	while(T--){
		int a, b, c, d, k;
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
		if(b > d) swap(b, d);
		printf("Case %d: ", caseno++);
		if(k == 0 || k > d){
			printf("0\n");
			continue;
		}
		b /= k;
		d /= k;
		long long ans = phi[b];//phi[i] stores the sum of phi(j) (1 <= j <= i).
		for(int i = b + 1; i <= d; ++i){
			ans += inclusion_exclusion(b, i);
			
		}
		printf("%I64d\n", ans);
	}
	return 0;
}