正经题解｜ X Y A B

题目分析

$[x,y]$ 中共有 $x - y + 1$ 个数。

我们很容易想到，找 $[1,n]$ 中所有能被 $k$ 整除数的个数即为 $\lfloor\frac{n}{k}\rfloor$。

能被 $a$ 或 $b$ 整除的数都是不满足条件的数。

那么设 $[1,y]$ 中所有不满足条件的数的个数为 $P_1$, $[1,x)$ 中所有不满足条件的数的个数为 $P_2$。

但是 $A$ 中 与 $B$ 中会重复统计 $a$ 与 $b$ 的公倍数，这个也很好处理，求 $a,b$ 的最小公倍数，计算不满足条件的个数减去即可。这里设 $a,b$ 的最小公倍数为 $k$。

$P_1 = \lfloor\frac{y}{a}\rfloor + \lfloor\frac{y}{b}\rfloor - \lfloor\frac{y}{k}\rfloor$

$P_2 = \lfloor\frac{x-1}{a}\rfloor + \lfloor\frac{x-1}{b}\rfloor - \lfloor\frac{x-1}{k}\rfloor$

答案则为：$x - y + 1 - P_1 - P_2$。

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll gcd(ll a,ll b) {
    if (a % b == 0)return b;
    return gcd(b,a%b);
}
int main() {
    ll x,y,a,b;
    cin >> x >> y >> a >> b;
    ll k = a * b / gcd(a,b);
    x--;
    ll cnt = (y / a + y / b - y / k) - (x / a + x / b - x / k);
    cout << y - x - cnt << endl;
    return 0;
}