NC16513 - 无关

题意

给你一个集合，如果一个数字不能被集合里面任意一个数字整除，那么这个数字与这个集合无关，问你区间中有多少个这种数字

数据范围

集合中都是素数

思路

首先我们可以根据前缀和的思想，把问题变成中与无关的个数减去中与无关的个数，

那么问题变成求解中与无关的整数个数，

我们设表示性质: 可以被整除

那么我们其实要求解的就是:

根据容斥原理可得

代码

/**
 *    author: andif
 *    created: 28.08.2023 23:14:10
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;

int main() {
    qc;
    ll L, R; cin >> L >> R;
    int k; cin >> k;
    vi a(k);
    rep(i, 0, k) cin >> a[i];

    auto gao = [&] (ll x) {
        ll ret = x;
        rep(i, 1, (1 << k)) {
            int fg = __builtin_popcount(i) & 1 ? -1 : 1;
            ll cur = x;
            rep(j, 0, k) {
                if (i & (1 << j)) {
                    cur /= a[j];
                }
            }
            ret = ret + fg * cur;
        }
        return ret;
    };
    ll sumR = gao(R), sumL = gao(L - 1);
    cout << sumR - sumL << '\n';
    return 0;
}