Inclusion exclusion principle acwing 890 Divisible number

Principle of tolerance and exclusion AcWing 890. The number divisible

Original link

AcWing 890. The number divisible

Algorithm tags

Principle of tolerance and exclusion

Ideas

Excerpt from the solution

Code

#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 20;
int a[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read(), m=read();
    rep(i, 0, m){
        a[i]=read();
    }
    int res=0;
    //  Enumerate from 1  To  1111...(m individual 1) Every set state of , ( Select at least one set )
    rep(i, 1, 1<<m){
        // t Represents the product of prime numbers  cnt Indicates the number of current selection sets 
        int t=1, cnt=0;
        rep(j, 0, m){
            if(i>>j&1){
            	//  The product is greater than n,  be n/t = 0,  Jump out of this cycle 
                if(t*a[j]>n){
                    t=-1;
                    break;
                }
                cnt++;
                t*=a[j];
            }
        }
        if(t!=-1){
            if(cnt%2){
                res+=n/t;
            }else{
                res-=n/t;
            }
        }
    }
    printf("%lld", res);
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support