Hdu 1695 GCD (数论容斥原理)-蒲公英云

Hdu 1695 GCD (数论容斥原理)

参考了：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;
}