HDU - 1796How many integers can you find - （容斥定理）

Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.

Input

  There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.

Output

  For each case, output the number.

Sample Input

12 2
2 3      

Sample Output

7      

題意：給出n和m，然後給出一個m個數的集合，讓求小于n的數（1~n-1）裡面可以被集合中至少一個數整除的數的個數，

這是一個容斥定理的簡單的應用題，做這個題思路還是很清晰的，首先第一個坑就是，a[i]可能為0，而0是不能做除數的，是以要去掉集合中的0，那麼接下來用容斥原理的思路就是，找出1~n-1中可以被每個a[i]整除的數的個數，減去可以被集合中任意兩個數整除的數的個數，即可以整除任意兩個數最小公倍數的數的個數，加上可以被集合中任意三個數整除的數的個數。。。。。。

關于二進制運算原理參考：HDU - 4135 - Co-prime - （容斥原理，分解質因數）

代碼：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define M 15

ll n,m,num;
ll a[M];

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

ll solve()
{
    ll sum=0;
    for(ll msk=1;msk<(1ll<<num);msk++) //枚舉集合中所有數的所有組合情況
    {
        bool flag=true;
        ll mult=1,bits=0;
        for(ll i=0;i<num;i++)          //判斷哪些a[i]在目前排列中
        {
            if(msk&(1ll<<i))           //在排列中
            {
                ll temp=lcm(a[i],mult); //求其最小公倍數
                if(temp<n)             //必須是小于n的數
                {
                    ++bits;            //記錄個數
                    mult=temp;
                }
                else{
                    flag=false;
                    break;
                }
            }
        }

        if(flag==false)               //如果目前組合已經大于n是不符合題意的
            continue;
        ll cur=(n-1)/mult;            //可以被mult整除的數的個數
        if(bits&1)                    //奇加偶減
            sum+=cur;
        else
            sum-=cur;
    }
    return sum;
}

int main()
{
    int i;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        ll t;
        num=0;
        for(i=0;i<m;i++)
        {
            scanf("%lld",&t);
            if(t!=0)
            {
                a[num++]=t;
            }
        }
        sort(a,a+num);
        printf("%lld\n",solve());
    }

    return 0;
}
           

看到dfs的解法：http://blog.csdn.net/wyt734933289/article/details/51292489，這裡dfs要比簡單容斥快

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

int n, m;
int a[25];
ll ans, lcm;

ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a%b);
}

void dfs(int cur, ll val, int flag)
{
    for(int i = cur; i <= m; i++)
    {
        if(a[i])
        {
            lcm = a[i] / gcd(val, a[i]) *val;
            if(lcm > n) continue;//當lcm > n,就沒有必要繼續下去，因為再怎麼加 n/lcm也是0，ans不會有任何變化
            ans += flag * ( n / lcm );
            dfs(i + 1, lcm, -flag);
        }
    }
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 1; i <= m; i++)
        {
            scanf("%d", &a[i]);
        }
        n--;
        ans = 0;
        dfs(1, 1, 1);
        printf("%I64d\n", ans);
    }
    return 0;
}