能被整除的数

这里要求因子都是质数，质数的最小公倍数就是乘积，因此不需要单独求解最小公倍数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
typedef long long LL;
int a[N];
int n,m;
int main()
{
    cin>>n>>m;
    for (int i=0;i<m;i++) cin>>a[i];  //输入m个数

    int ans=0;
    for (int i=1;i<1<<m;i++)  //至少选择一个集合(如00001,0100000等)，最多是11111...11(共m个1)个集合
    {
        int t=1;  //t记录选中的集合的质数的乘积
        int cnt=0;  //cnt记录选中了多少个集合，便于后期确定对每个集合的加减
        for (int j=0;j<m;j++)  //把当前的i(实际是二进制数)的每一位取出来看一下，当前集合是否取
        {
            if (i>>j&1)  //这个位置是1，代表这个集合取
            {
                if ((LL)t*a[j]>n)
                {
                    t=-1;
                    break;
                }
                cnt++;   //取了一个集合了
                t=t*a[j];  //更新一下t
            }
        }

        if (t!=-1)  //合法的
        {
            if (cnt%2) ans+=n/t;  //取的集合数量时奇数个是加
            else ans-=n/t;   //偶数个是减
        }
    }
    cout<<ans<<endl;
    return 0;
}

对因子不做要求，质数和合数均可，就只需要单独求解一下最小公倍数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
typedef long long LL;
int a[N];
int n,m;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
int main()
{
    cin>>n>>m;
    for (int i=0;i<m;i++) cin>>a[i];  //输入m个数

    int ans=0;
    for (int i=1;i<1<<m;i++)  //至少选择一个集合(如00001,0100000等)，最多是11111...11(共m个1)个集合
    {
        int t=1;  //t记录选中的集合的质数的乘积
        int cnt=0;  //cnt记录选中了多少个集合，便于后期确定对每个集合的加减
        for (int j=0;j<m;j++)  //把当前的i(实际是二进制数)的每一位取出来看一下，当前集合是否取
        {
            if (i>>j&1)  //这个位置是1，代表这个集合取
            {
                if ((LL)t*a[j]>n)
                {
                    t=-1;
                    break;
                }
                cnt++;   //取了一个集合了
                t=lcm(t,a[j]);  //更新一下t
            }
        }

        if (t!=-1)  //合法的
        {
            if (cnt%2) ans+=n/t;  //取的集合数量时奇数个是加
            else ans-=n/t;   //偶数个是减
        }
    }
    cout<<ans<<endl;
    return 0;
}