题目
题目描述
若一个集合A内所有的元素都不是正整数N的因数，则称N与集合A无关。
给出一个含有k个元素的集合A={a1,a2,a3,...,ak}，求区间[L,R]内与A无关的正整数的个数。
保证A内的元素都是素数。
输入描述
输入数据共两行：
第一行三个正整数L,R,k，意义如“题目描述”。
第二行k个正整数，描述集合A，保证k个正整数两两不相同。
输出描述
输出数据共一行：
第一行一个正整数表示区间[L,R]内与集合A无关的正整数的个数
示例1
输入
1 10 4
2 3 5 7
输出
1
示例2
输入
2 10 4
2 3 5 7
输出
0
说明
对于30%的数据：1<=L<=R<=10^6
对于100%的数据：1<=L<=R<=10^18,1<=k<=20,2<=ai<=100
题解
知识点：容斥原理，数论。
经典容斥题，我们将 \([l,r]\) 拆成 \([1,l-1],[1,r]\) ，分别计算两边然后减一下就行。
众所周知， \([1,n]\) 中 \(d\) 的倍数个数有 \(\left\lfloor \dfrac{n}{d} \right\rfloor\) 。接下来考虑容斥，比如去掉 \(2,3,5\) 的倍数，那么计算过程为：
\[\begin{aligned}
&+ \left\lfloor \dfrac{n}{1} \right\rfloor\\
&- \left( \left\lfloor \dfrac{n}{2} \right\rfloor + \left\lfloor \dfrac{n}{3} \right\rfloor + \left\lfloor \dfrac{n}{5} \right\rfloor \right) \\
&+ \left( \left\lfloor \dfrac{n}{2\cdot3} \right\rfloor + \left\lfloor \dfrac{n}{2\cdot 5} \right\rfloor + \left\lfloor \dfrac{n}{3 \cdot 5} \right\rfloor \right) \\
&- \left\lfloor \dfrac{n}{2 \cdot 3 \cdot 5} \right\rfloor\\
\end{aligned}
\]
时间复杂度 \(O(2^k)\)
空间复杂度 \(O(k)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[27];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll l, r;
int k;
cin >> l >> r >> k;
for (int i = 1;i <= k;i++) cin >> a[i];
ll ans = 0;
for (int mask = 0;mask < (1 << k);mask++) {
ll mul = 1;
bool f = 0;
for (int i = 0;i < k;i++)
if (mask >> i & 1) mul = min((__int128_t)mul * a[i + 1], (__int128_t)1e18 + 1), f ^= 1;
if (mul > 1e18) continue;
ans += (f ? -1 : 1) * (r / mul - (l - 1) / mul);
}
cout << ans << '\n';
return 0;
}