How many integers can you find————（算术基本定理+容斥）

水深无声 2022-05-18 00:11 173阅读 0赞

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<231,0<M<=10  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个数的集合，让你从\[1,N−1\]  \[ 1 , N − 1 \] 里边找到能够被集合里边任意一个数整除的数的个数，  
eg：N=12，M=\{ 2,3\}  N = 12 ， M = \{ 2 , 3 \}   
所以ans=7  a n s = 7

数字构成的集合就是

\{ 2,3,4,6,8,9,10\}  \{ 2 , 3 , 4 , 6 , 8 , 9 , 10 \}

--------------------

//#include<bits/stdc++.h>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    using namespace std;
    typedef long long ll;
    ll gcd(ll a,ll b)
    {
        return !b?a:gcd(b,a%b);
    }
    ll lcm(ll a,ll b)
    {
        return a/gcd(a,b)*b;
    }
    ll a[30];
    int main()
    {
        ll n,m;
        while(~scanf("%lld %lld",&n,&m))
        {
            memset(a,0,sizeof(a));
            for(ll i=0;i<m;i++)
            {
                scanf("%lld",&a[i]);
                if(a[i]<1||a[i]>=n)
                {
                    i--;
                    m--;
                }
             } 
            ll ans=0;
            for(ll i=1;i<(1<<m);i++){
                ll cnt=0;   ll LCM=1;
                for(ll j=0;j<m;j++){
                    if(1&(i>>j)){
                        cnt++;
                        LCM=lcm(a[j],LCM);
                    }   
                }   
                if(cnt&1)   ans+=(n-1)/LCM;
                else        ans-=(n-1)/LCM;
            }   
            printf("%lld\n",ans);
        }
        return 0;
    }