容斥定理

#include<cstdio>
#include<algorithm>
using namespace std;
long long Gcd(long long a,long long b){
    return b==0?a:Gcd(b,a%b);
}
long long cal(long long n,int *p,int cnt){
    long long res=0;
    for(int i=1;i<(1<<cnt);i++){
        int t=i,tmp=1,k=0;
        int len=0;
        while(t){
            if(t&1){
                tmp=tmp/Gcd(tmp,p[k])*p[k];
                len++;
            }
            t>>=1;
            k++;
        }
        if(len&1) res+=n/tmp;
        else res-=n/tmp;
    }
    return res;
}

int main(){
    long long n;
    int m,Set_m[20+5];
    while(scanf("%I64d%d",&n,&m)==2){
        int k=0;
        while(m--){
            scanf("%d",&Set_m[k]);
            if(Set_m[k]) k++;
        }
        sort(Set_m,Set_m+k);
        printf("%I64d
",cal(n-1,Set_m,k));
    }

}