题目描述

给定一个长度为n的序列a1..an，求m以内的不能被a1..an中任意一个ai整除的正整数有多少个？

 

输入

第一行两个数n,m
接下来一行n个数，a1..an

 

 

输出

共一个数，即m以内的不能被a1..an中任意一个ai整除的正整数有多少个。

 

样例输入

3 2015
4 5 6

样例输出

1075

 

提示

对于 30% 的数据，1≤m≤100000
对于另外 30% 的数据，n=3
对于 100% 的数据，1≤n≤20, 1≤m≤10^18, 1≤ ai≤10^9

思路很简单，容斥原理，但是状压一直超时，卑微

丧心病狂的剪枝优化

代码1：无剪枝状压

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[30];
ll n,m;
ll lcm(ll a,ll b){
    return a/__gcd(a,b)*b;
}
bool judge(ll a,ll b){
    ll c=m/a;
    return b<=c;
}
int main(){
    scanf("%lld%lld",&n,&m);
    int N=0;
    for(int i=0;i<n;i++){
        ll x;
        scanf("%lld",&x);
        if(x<=m) a[N++]=x;
    }
    ll ans=0;
    for(int i=1;i<(1<<N);i++){
        int cnt=0;
        ll down=1;
        for(int j=0;j<N;j++){
            if(i&(1<<j)){
                cnt++;
                if(judge(down,a[j]/__gcd(down,a[j])))
                down=lcm(down,a[j]);
                else{
                    down=m+1;
                    break;  
                }
            }
        }
        if(down==m+1) continue;
        if((cnt&1)) ans+=m/down;
        else ans-=m/down;
    }
    printf("%lld\n",m-ans);
     
    return 0;
}

代码2：剪枝+状压

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[30];
int n;
ll m;
ll gcd;
ll lcm(ll a,ll b){
    return a/gcd*b;
}
bool judge(ll a,ll b){
    return b<=m/a;
}
bool cmp(ll a,ll b){
    return a>b;
}
int main(){
    scanf("%d%lld",&n,&m);
    int N=0;
    ll x;
    bool flag=true;
    for(int i=0;i<n;i++){    
        scanf("%lld",&x);
        if(x<=m) a[N++]=x;
        if(x==1) flag=false;
    }
    sort(a,a+N,cmp);
    ll ans=0;
    if(flag){
        for(int i=1;i<(1<<N);i++){
            int cnt=0;
            ll down=1;
            for(int j=0;j<N;j++){
                if(i<(1<<j)) break;
                if(i&(1<<j)){
                    cnt++;
                    gcd=__gcd(down,a[j]);
                    if(judge(down,a[j]/gcd))
                    down=lcm(down,a[j]);
                    else{
                        down=m+1;
                        break;  
                    }
                }
            }
            if(down==m+1) continue;
            if((cnt&1)) ans+=m/down;
            else ans-=m/down;
        }
    }
    else ans=m;
    printf("%lld\n",m-ans); 
    return 0;
}

代码3：无剪枝+dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll m,ans;
ll a[30];
bool judge(ll a,ll b){
    return b<=m/a;
}
void dfs(int now,int num,ll down){
    if(now==n){
        if(num&1) ans+=m/down;
        else if(num!=0) ans-=m/down;
        return ;
    }
    ll gcd=__gcd(down,a[now]);
    if(judge(down/gcd,a[now])) dfs(now+1,num+1,down/gcd*a[now]);
    dfs(now+1,num,down);
}
int main(){
    scanf("%d%lld",&n,&m);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    ans=0;
    dfs(0,0,1);
    printf("%lld\n",m-ans);
    return 0;
}

代码4：剪枝+dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll m,ans;
ll a[30];
bool cmp(ll a,ll b){
    return a>b;
}
bool judge(ll a,ll b){
    return b<=m/a;
}
void dfs(int now,int num,ll down){
    if(now==n){
        if(num&1) ans+=m/down;
        else if(num!=0) ans-=m/down;
        return ;
    }
    ll gcd=__gcd(down,a[now]);
    if(judge(down/gcd,a[now])) dfs(now+1,num+1,down/gcd*a[now]);
    dfs(now+1,num,down);
}
int main(){
    scanf("%d%lld",&n,&m);
    int cnt=0;
    bool flag=true;
    for(int i=0;i<n;i++) {
        ll x;
        scanf("%lld",&x);
        if(x<=m) a[cnt++]=x;
        if(x==1) flag=false;
    }
 
    n=cnt;
    if(flag){   
        sort(a,a+n,cmp);
        ans=0;
        dfs(0,0,1);
    }
    else{
        ans=m;
    }
    printf("%lld\n",m-ans);
    return 0;
}