hdu1695(容斥原理)

2017年07月22日 9点热度 0人点赞 0条评论

求(1,b)区间和(1,d)区间里面gcd(x, y) = k的数的对数(1<=x<=b , 1<= y <= d)。

b和d分别除以k之后的区间里面,只需要求gcd(x, y) = 1就可以了,这样子求出的数的对数不变。

这道题目还要求1-3 和 3-1 这种情况算成一种,因此只需要限制x

只需要枚举x,然后确定另一个区间里面有多少个y就可以了。因此问题转化成为区间(1, d)里面与x互素的数的个数

先求出x的所有质因数,因此(1,d)区间里面是x的质因数倍数的数都不会与x互素,因此,只需要求出这些数的个数,减掉就可以了。

如果w是x的素因子,则(1,d)中是w倍数的数共有d/w个。


容斥原理:

所有不与x互素的数的个数= 1个因子倍数的个数 - 2个因子乘积的倍数的个数 + 3个……-……


答案很大,用long long。

所有数的素因子,预先处理保存一下,不然会超时的。

#include
#include
#include
using namespace std;
const int mx=100010;
int a,b,c,d,k;
vector x[mx];
int vis[mx];
void prime(){
	for(int i=2;id) swap(b,d);
		for(int i=1;i<=d;++i)
		{
			k=min(i,b);//求i和区间(1,k)的值
			ans+=k;
			for(int j=1;j<(1<
未经允许不得转载!hdu1695(容斥原理)

update

纸上得来终觉浅, 绝知此事须躬行。