[NOIP2009] Hankson的趣味题

[NOIP2009] (Hankson)的趣味题

题目大意:给出(a_0, a_1,b_0,b_1),求有多少(x)满足(gcd(x,a_0) = a_1)且(lcm(x,b_0)=b_1)

Solution

可知(x)一定是(b_1)的因子,也一定是(a_1)的整数倍,可以从(1)到(sqrt b_1)枚举数字(x)和(b_1/x),如果为(a_1)的倍数且可以满足那两个式子,就说明符合,当然这是一个比较蠢的枚举方法

Code

#include <cstdio>
#include <cmath>

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int n = read();
    while (n--) {
        int a0 = read(), a1 = read(), b0 = read(), b1 = read();
        int m = sqrt(b1) + 0.5, ans = 0;
        for (int x = 1; x <= m; x ++) {
            if (b1 % x) continue;
            if (gcd(x, a0) == a1 && x / gcd(x, b0) * b0 == b1) ++ans;
            if ((b1 / x) % a1 || b1 / x == x) continue;
            if (gcd(b1 / x, a0) == a1 && b1 / x / gcd(b1 / x, b0) * b0 == b1) ++ans;
        }
        printf("%d
", ans);
    }
    return 0;
}