首页 > 代码库 > HDU1796 How many integers can you find【容斥定理】

HDU1796 How many integers can you find【容斥定理】

题目链接:

http://acm.hdu.edu.cn/showproblem.php?

pid=1796


题目大意:

给你一个整数N。和M个整数的集合{A1、A2、…、Am}。集合内元素为非负数(包括零),求小于N的

正整数(1~N-1)中,能被M个整数的集合中随意一个元素整除的正整数个数。

比如N = 12。M = {2,3},在1~N-1中,能被2整除的数为{2,4,6。8。10},能被3整除的数为

{3。6,9}。则所求集合为{2,3,4。6,8,9,10},共7个,则答案为7。


思路:

就是求M个集合的并集。先看上边的样例。能被2整除的数集合S1为{2,4,6,8。10},能被3整除的数

集合S2为{3,6。9}。而两者交集S12为能被LCM(2,3) = 6整除的数为{6}。

则两者并集 S = S1 + S2 - S12。

依据容斥定理得:若有M个数,则可求出1~N-1中能被不同组合的公倍数整除的个数。

1~N-1能被公倍数整除的个数为  (N-1) / LCM。然后依据奇数项加,偶数项减的原则得出答案个数。


AC代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;

int Gcd(int a,int b)
{
    if(a < b)
        int temp = a, a = b, b = temp;
    if(b == 0)
        return a;
    return Gcd(b,a%b);
}

int Lcm(int a,int b)
{
    return a/Gcd(a,b)*b;
}

int N,M;
int A[220],Select[220];

int Solve()
{
    int ans = 0;
    for(int i = 1; i < (1 << M); ++i)
    {
        int odd = 0;
        for(int j = 0;  j < M; ++j)
        {
            if((1<<j) & i)
            {
                Select[++odd] = j;
            }
        }
        int LCM = 1;
        for(int j = 1; j <= odd; ++j)
            LCM = Lcm(LCM,A[Select[j]]);
        if(odd & 1)
            ans += N/LCM;
        else
            ans -= N/LCM;
    }
    return ans;
}

int main()
{
    int d;
    while(~scanf("%d%d",&N,&M))
    {
        for(int i = 0; i < M; ++i)
        {
            scanf("%d",&d);
            if(d)
                A[i] = d;
            else
                i--,M--;
        }
        N--;
        printf("%d\n",Solve());
    }

    return 0;
}


HDU1796 How many integers can you find【容斥定理】