跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:30:08

    【本题解由站长编写】

    x 必须整除 b1(lcm(x,b0)=b1 的必要条件),所以枚举 b1 的约数:d 扫到 √b1,对每个满足整除的 d 同时检查 d 与 b1/d。先做 x%a1 的廉价预筛再做两个 gcd;b1≤2×10⁹ 用 32 位除法加速即可通过 n≤2000。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
    bool check(long long x, long long a0, long long a1, long long b0, long long b1) {
        if (x % a1) return false;
        if (gcd(x, a0) != a1) return false;
        long long g = gcd(x, b0);
        return x / g * b0 == b1;
    }
    int main() {
        int n; 
        scanf("%d", &n);
        while (n--) {
            long long a0, a1, b0, b1;
            scanf("%lld %lld %lld %lld", &a0, &a1, &b0, &b1);
            unsigned b = (unsigned)b1;
            unsigned lim = (unsigned)sqrt((double)b);
            while ((unsigned long long)(lim + 1) * (lim + 1) <= b) lim++;
            long long cnt = 0;
            for (unsigned d = 1; d <= lim; d++)
                if (b % d == 0) {
                    if (check(d, a0, a1, b0, b1)) cnt++;
                    if ((unsigned long long)d * d != b && check(b1 / d, a0, a1, b0, b1)) cnt++;
                }
            printf("%lld\n", cnt);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    4248
    时间
    1000ms
    内存
    64MiB
    难度
    5
    标签
    递交数
    1
    已通过
    0
    上传者