1. 求1~n中有多少个数至少能被p[i]里一个的数整除

#include <iostream>
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 & 1) res += n / t;
            else res -= n / t;
        }
    }

    cout << res;
    return 0;
}

2. 214. Devu和鲜花

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 21,mod = 1e9 + 7 ;

LL n , m;
LL a[N];
int down = 1;

int qmi(int a, int k)
{
    int res = 1 ;
    while (k)
    {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int C(LL a,LL b) {
    if (a < b) return 0;
    int up = 1;
    for(LL i = a; i > a - b ; --i) up = i % mod * up % mod;
    return (LL)up * down % mod;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i <= n - 1; ++i) down = (LL)i * down % mod;
    down = qmi (down , mod - 2);

    LL res = 0;
    for (int i = 0; i < 1 << n; i++)
    {
        LL flag = 1,d = m + n - 1;
        for (int j = 0; j < n; j++)
        {
            if (i >> j & 1)
            {
                flag *= -1;
                d -= a[j] + 1; 
            }
        }
        res = (res + flag * C(d , n - 1)) % mod;
    }
    cout << (res + mod) % mod;
    return 0;
}