BZOJ 2301 Problem b

发表于 | 更新于

Link

Solution

裸的反演

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=5e4,MAXN=N+10;
typedef long long LL;
using std::min;
using std::swap;
int mu[MAXN],prime[MAXN],pcnt,Mu[MAXN];
void Prep()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
		{
			prime[++pcnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++) Mu[i]=Mu[i-1]+mu[i];
}
LL Count(int x,int y)//互质的个数
{
	LL res=0;
	if(x>y) swap(x,y);
	for(int i=1,last=1;i<=x;i=last+1)
	{
		last=min(x/(x/i),y/(y/i));
		res+=(LL)(Mu[last]-Mu[i-1])*(x/i)*(y/i);
	}
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	Prep();
	int T;red(T);
	while(T--)
	{
		int a,b,c,d,K;red(a),red(b),red(c),red(d),red(K);
		printf("%lld\n",Count(b/K,d/K)+Count((a-1)/K,(c-1)/K)-Count((a-1)/K,d/K)-Count(b/K,(c-1)/K));
	}
	return 0;
}