2023-9-10 能被整除的数

题目链接：能被整除的数

文章来源地址https://uudwc.com/A/PmnAo

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int n, m;
int p[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];
    
    int res = 0;
    for(int i = 1; i < 1 << m; i++)
    {
        int t = 1, cnt = 0;
        for(int j = 0; j < m; j++)
            if(i >> j & 1)
            {
                cnt ++;
                if((LL) t * p[j] > n) 
                {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        if(t != -1){
            if(cnt % 2) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    
    return 0;
}