[Hdu4497]GCD and LCM

OI 题解 数论 数学

算法：数论

1. 如果$G\nmid L$，不合法，输出零。
2. 对$L$和$G$，分别唯一分解，对于某个质因子$p_i$，其指数为$k_L,k_G$，如果$k_L=k_G$，那么$(x, y, z)$的$p_i$的指数只能为$k_L$，如果$k_L\neq k_G$，那么$(x, y, z)$中必有一个数$p_i$的指数为$k_L$，一个为$k_G$，一个满足$k_G\le k\le k_L$，这样的三元组一共有$6(k_L-k_G)$种。

代码

这里做了一个小改动：直接分解$L/G$

本来还打了素数表，不知道为什么WA了

#include<cstdio>
#include<cstring>
#define ll long long
const int N = (1 << 20) + 10;
ll l[N], g[N];
ll L, G;
inline void factor() {
    memset(g, 0, sizeof(g));
    memset(l, 0, sizeof(l));
    if (L % G) {
        printf("0\n");
        return;
    }
    ll ans = 1;
    L /= G;
    for (register int i = 2; L > 1; ++i) {
        int cnt = 0;
        while (L % i == 0 && L > 1) {
            L /= i;
            cnt++;
        }
        if (cnt) ans *= 6 * cnt;
    }
    printf("%d\n", ans);
}
int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%lld %lld", &G, &L);
        factor();
    }
    return 0;
}