【NC16610】Hankson的趣味题

题目

Hankson的趣味题

枚举，最大公约数，最小公倍数

思路

根据题意，可以获得以下信息：

1. 当 $a_0\ne a_1$ 时，$x$ 是 $a_0$ 的倍数但不是 $a_1$ 的倍数
2. 当 $b_0\ne b_1$ 时，$x$ 是 $b_1$ 的约数但不是 $b_0$ 的约数

在上面的信息，有一条值得注意的信息：$x$ 是 $b_1$ 的约数，这就是切入此题的关键

枚举所有 $b_1$ 的约数，然后判断其是否与 $a_0$ 的最大公约数是 $a_1$，判断其是否与 $b_0$ 的最小公倍数是 $b_1$

由于此题的数据最大为 $10^9$ 数量级的，枚举其所有约数使用朴素的 $O(\sqrt{n})$ 的算法时间复杂度是 $10^{4.5}$ 级别，在外面再套一个 $10^3$ 级别的组数，总时间是 $10^{7.5}$ 级别的，是可以过的（一般以 $10^8$ 作为能不能过的评判标准）。

代码

#include <stdio.h>

int gcd(int m, int n) {
    int t = 0;
    while (n) {
        t = m % n;
        m = n;
        n = t;
    }
    return m;
}

int lcm(int m, int n) { return m / gcd(m, n) * n; }

int main(void) {
    int t = 0, a0 = 0, a1 = 0, b0 = 0, b1 = 0;
    scanf("%d", &t);
    int ans = 0, i = 0;
    while (t--) {
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        ans = 0;
        for (i = 1; i * i <= b1; i++) {
        	// 枚举 b1 的所有约数
            if (b1 % i == 0) {
            	// 判断约数是否满足题目条件
                if (gcd(i, a0) == a1 && lcm(i, b0) == b1) ans++;
                if (b1 / i == i) {
                	// 此时已经是枚举的最后一个数了，直接退出也无妨
                    break;
                }
                if (gcd(b1 / i, a0) == a1 && lcm(b1 / i, b0) == b1) ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}