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 <memory.h>
#include <cstdio>
#include <vector>
using namespace std;
const int MAX = 100010;
vector<int> 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;
}

HDU 1695 GCD(欧拉函数＋容斥原理),布布扣,bubuko.com

HDU 1695 GCD(欧拉函数＋容斥原理)

原文：http://blog.csdn.net/zxjcarrot/article/details/20840639