输入a b c d k求有多少对x y 使得x在a-b区间 y在c-d区间 gcd(x, y) = k 此外a和c一定是1

由于gcd(x, y) == k 将b和d都除以k 题目转化为1到b/k 和1到d/k 2个区间 如果第一个区间小于第二个区间 讲第二个区间分成2部分来做1-b/k 和 b/k+1-d/k

第一部分对于每一个数i 和他互质的数就是这个数的欧拉函数值 全部数的欧拉函数的和就是答案

第二部分能够用全部数减去不互质的数 对于一个数i 分解因子和他不互质的数包括他的若干个因子 这个用容斥原理 奇加偶减

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef __int64 LL;

const int maxn = 100010;

LL phi[maxn];

LL sum[maxn], p[maxn][33];

void phi_table(int n)

{

	memset(sum, 0, sizeof(sum));

	memset(phi, 0, sizeof(phi));

	phi[1] = 1;

	for(int i = 2; i <= n; i++)

	{

		if(!phi[i])

			for(int j = i; j <= n; j += i)

		 	{

		 		if(!phi[j])

				 	phi[j] = j;

			 	phi[j] = phi[j] / i * (i-1);

			 	p[j][sum[j]++] = i;

		 	}

	 	phi[i] += phi[i-1];

	}

}

void dfs(int id, LL num, LL cnt, int a, LL& ans, int x)

{

	if(id == sum[x])

	{

		if(cnt == 0)

			return;

		if(cnt&1)

			ans += a/num;

		else

			ans -= a/num;

		return;

	}

	dfs(id+1, num*p[x][id], cnt+1, a, ans, x);

	dfs(id+1, num, cnt, a, ans, x);

}

LL cal(int x, int a)

{

	LL ans = 0;

	dfs(0, 1, 0, a, ans, x);

	return ans;

}

int main()

{

	phi_table(100000);

	int cas = 1;

	int T;

	scanf("%d", &T);

	while(T--)

	{

		int a, b, k;

		scanf("%d %d %d %d %d", &a, &a, &b, &b, &k);

		if(!k)

		{

			printf("Case %d: %d\n", cas++, 0);

			continue;

		}

		if(a > b)

			swap(a, b);

		a /= k;

		b /= k;

		LL ans = phi[a];

		for(int i = a+1; i <= b; i++)

			ans += a-cal(i, a);

		printf("Case %d: %I64d\n", cas++, ans);

	}

	return 0;

}