Hdu 1695 GCD (数论容斥原理)

落日映苍穹つ 2022-08-26 08:10 160阅读 0赞

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

题意：求（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<y。

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

①(1...b)与(1...b)中有多少对数互质  
②(1...b)与(b+1...d)中有多少对数互质

问题1就是欧拉函数的应用，下面的代码没有用这个，直接和问题2一起解决，牺牲了一些速度。

问题2从反面考虑，对于(b+1...d)中的每一个y，要想知道(1...b)中有多少数与它互质，  
我们只需要知道多少个数与它不互质即可。而两个数不互质就意味着它们有公因子。  
对于每一个y的因子f，都能确定地知道(1...b)中有多少个数含有因子f，用容斥原理算一下，  
就能知道(1...b)中有多少个数与y互质了。枚举y即可解决问题。

如果w是x的因子，则（1，d）中是w倍数的数共有d/w个。

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

以下转自AC神：http://hi.baidu.com/aekdycoin/item/4c8d4089e5011759840fabad

关于区间gcd统计的小问题  
1.求\[1,n\]内和n的gcd=k的个数  
转换为求区间\[1,n/k\]内和n/k互质的数的个数  
2.求\[1,m\]内和n互质的数的个数  
容斥原理  
3.求\[1,m\]内和n的gcd=k的个数  
转化模型,同上

#include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=100005;
    
    vector<int> data[N];
    bool tag[N];
    
    void Prime ()
    {//预处理素数,同时记录每一个数的素因子
    	int i,j;
    	memset(tag,false,sizeof(tag));
    	for (i=0;i<N;i++)
    		data[i].clear();
    	for (j=2;j<N;j+=2)
    		data[j].push_back(2);
    	for (i=3; i<N; i+=2) if (tag[i]==false)
    		for (j=i;j<N;j+=i)
    		{
    			tag[j] = true;
    			data[j].push_back(i);
    		}
    }
    
    int Deal (int u,int state,int id)
    {
    	int cnt=0,v=1;  //v 因子
    	for (int i=0; i<data[id].size(); i++)
            if ((1<<i) & state)
    		{
    			cnt++;
    			v *= data[id][i];
    		}
    	int all=u/v;
    	if (cnt%2==0)
    		return -all;
    	else
    		return all;
    }
    
    int main ()
    {
    	Prime();
    	int T;
    	scanf("%d", &T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		int b,d,k;
    		scanf("%*d%d%*d%d%d",&b,&d,&k);
    		if (k==0)
    		{
    			printf("Case %d: 0\n",Cas);
    			continue;
    		}
    		b/=k;
    		d/=k;
    		
    		if (b>d)
    			swap(b,d);
    		__int64 ans=0;
    		for (int i=1;i<=d;i++)
    		{//枚举y,求1~d中与x互素的个数
    			int x=min(i,b);
    			ans+=x; //假设全都互素,然后减掉不互素的
    			for (int j=1;j<(1<<data[i].size());j++)
    				ans -= Deal(x,j,i);
    		}
    		printf("Case %d: %I64d\n",Cas,ans);
    	}
    	return 0;
    }

[HDU 1695 GCD _ - _ - _ - CSDN.NET]: http://blog.csdn.net/yang_7_46/article/details/9072533