算法
(容斥原理)
令 $f(X)$ 为不超过 $X$ 的不能被 $C$ 或 $D$ 整除的个数
于是原问题就变成了求 $f(B) - f(A - 1)$
$1 \sim X$ 中不能被 $C$ 整除的个数为 $X$ - 可以被 $C$ 整除的数的个数($\lfloor \frac{X}{C} \rfloor$)
$1 \sim X$ 中不能被 $D$ 整除的个数为 $X$ - 可以被 $D$ 整除的数的个数($\lfloor \frac{X}{D} \rfloor$)
注意到可以被 $C$ 整除的数中可能存在能被 $D$ 整除的数
所以,$1 \sim X$ 中不能被 $C$ 或 $D$ 整除的个数为 $X - \lfloor \frac{X}{C} \rfloor - \lfloor \frac{X}{D} \rfloor + \lfloor \frac{X}{\rm LCM(CD)} \rfloor$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::gcd;
using ll = long long;
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll f(ll x, int c, int d) {
ll res = x;
res -= x / c;
res -= x / d;
res += x / lcm(c, d);
return res;
}
int main() {
ll a, b;
int c, d;
cin >> a >> b >> c >> d;
ll ans = f(b, c, d) - f(a - 1, c, d);
cout << ans << '\n';
return 0;
}
在q群里问过了,已经明白了,谢谢
1∼X 中不能被 C 整除的个数为 X - 可以被 CC 整除的数的个数(⌊X/C⌋)
1∼X 中不能被 D 整除的个数为 X - 可以被 DD 整除的数的个数(⌊X/D⌋)
如何证明上面的两个结论正确啊,我不理解,大佬可以说说吗