容斥原理（二进制实现）

链接：

hdu 1796 How many integers can you find

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 112;
ll a[maxn],num;
ll ***(ll x,ll y)
{
    return x%y==0?y:***(y,x%y);
}
ll LCM(ll x,ll y)
{
    return x*y/***(x,y);
}
ll rongchi(ll n)
{
    ll ans=0;
    for(ll i=1;i<(1<<num);i++)
    {
        ll cnt=0,lcm=-1;
        for(ll j=0;j<num;j++)    
        {
            if(i&(1<<j)) 
            {
                cnt++;
                if(lcm==-1) lcm=a[j];
                else lcm=LCM(lcm,a[j]);
            }
        }
        if(lcm==-1) continue;
        if(cnt&1) ans+=(n-1)/lcm;
        else ans-=(n-1)/lcm;
    }
    return ans; 
}
int main()
{
    ll n,m; 
    while(~scanf("%lld%lld",&n,&m))
    {
        ll x;
        num=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%lld",&x);
            if(x) a[num++]=x; 
        }
        printf("%lld\n",rongchi(n));
    }
    return 0;
}

链接：

hdu 4135 Co-prime

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 2;
ll a[maxn],num=0;
void getPrime(ll x)
{
	for(ll i=2;i*i<=x;i++)
		if(x%i==0)
		{
			a[num++]=i;
			while(x%i==0)
			{
				x/=i;
			}
		}
	if(x!=1) a[num++]=x;
}
ll ***(ll x,ll y) 
{
	return x%y==0?y:***(y,x%y);
}
ll LCM(ll x,ll y)
{
	return x*y/***(x,y);
}
ll rongchi(ll n)
{
	ll ans=0;
	for(ll i=1;i<(1<<num);i++)
	{
		ll cnt=0,lcm=-1;
		for(ll j=0;j<num;j++)
			if(i&(1<<j))
			{
				cnt++;
				if(lcm==-1) lcm=a[j];
				else lcm=LCM(lcm,a[j]);
			}	
		if(lcm==-1) continue; 
		if(cnt&1) ans+=n/lcm;
		else ans-=n/lcm;
	}
	return n-ans;
}
int main()
{
	int t,o=0;
	scanf("%d",&t);
	while(t--)
	{
		ll a,b,n;
		num=0;
		scanf("%lld%lld%lld",&a,&b,&n);
		getPrime(n);
		printf("Case #%d: %lld\n",++o,rongchi(b)-rongchi(a-1));
	}
	
	
	return 0;	
}