题解 | #小红的整数操作#

先分解质因数，然后将x,y都除以共同的质因数得到两个最小的组合，然后用最小的限制 l 除以x，y中的最小值（找到最小无法满足要求的组合，x *n 和 y *n，刚刚好整除时是可以满足条件的所以减一在除），同理用上限去除以最大值获得最大可以满足要求的组合x *m, y*m，从x *n 到x * m都是可以满足条件的，所以输出m-n和0的较大值，因为可以相减会有-1。

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, int> mp;
void get_prime(int n) {
    while (n % 2 == 0) {
        mp[2]++;
        n /= 2;
    }
    for (int i = 3; i * i < n; i += 2) {
        if (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }
    if (n > 2) {
        mp[n]++;
    }
}
int main() {
    int x, y, l, r;
    cin >> x >> y >> l >> r;
    get_prime(x);
    for (auto& iter : mp) {
        while (y % iter.first == 0 && x % iter.first == 0) {
            x /= iter.first;
            y /= iter.first;
        }
    }
    int h_throld = max(x, y), b_throld = min(x, y);
    int left = (l - 1) / b_throld, right = r / h_throld;
    int ans = max(0 ,right - left);
    cout << ans << endl;
}