HDU4497 GCD and LCM（唯一分解定理 & 排列组合）

题目大意

题目链接
给你两个数 L, G，问你有多少有序三元组$ (x,y,z) $ 满足
$$ gcd (x,y,z)=G $$
$$ lcm (x,y,z)=L $$

思路分析

如果组合存在时，则题目等同于 $ gcd(x, y, z) = 1 $ 且 $ lcm(x, y, z) = L/G $

令 $ a = L / G $

当 $ L $ % $ G $ $ != $ $0 $ 时, 无解

首先对 $ a $ 进行素数分解

$ a = p_1^{t_1} \cdot p_2^{t_2} \cdot…. \cdot p_n^{t_n} $

由于 $ a $ 是三个数的倍数，所以有

$ x = p_1^{i_1} \cdot p_2^{i_2} \cdot …. \cdot p_n^{i_n} $

$ y = p_1^{j_1} \cdot p_2^{j_2} \cdot…. \cdot p_n^{j_n} $

$ z = p_1^{k_1} \cdot p_2^{k_2} \cdot…. \cdot p_n^{k_n} $

对于某一个素因子 $ p $ ,需要满足 x，y，z 的最大公约数为1, 所以 $ min(i,j,k) = 0 $ 。

又因为要满足 $ x，y，z $ 的最小公倍数为a，即 $ p^t $ 必然要至少存在一个，所以 $max(i,j,k)=t$

换言之：至少要有一个 $p^t$ ,以满足 lcm 的要求；至多有两个包含$ p $ , 以满足 gcd 的要求。

因而基本的组合方式为 $ (0，p^t，p^k) $ , $ k \in (0, t) $

因为 $(1, 2, 3)$ 和 $(2, 1, 3)$ 是不同的方法，所有满足要求的方法中，除了 $(0, 0, t)$ 和 $(0, t, t) $ 各有3种排列之外，其余的 $(0, x, t)$ 当 $ (1 \le x \le t-1) $ 有6种排列。

对于某一个素因子 $ p $ 总的方法数为 $ 6 \cdot (t-1) + 2\cdot3 = 6 \cdot t $

因此总的方法数为 $ \prod{6 \cdot t_i} $

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
int T;
ll G, L;
ll p[N];

int main() {
    cin >> T;
    while(T--) {
        scanf("%lld%lld", &G, &L);
        ll tmp = L / G;
        if(L % G) {
            cout << 0 << endl;
            continue;
        }
        ll x = (ll)sqrt(tmp);
        memset(p, 0, sizeof(p));
        for(int i = 2; i <= x; i++) {
            while(tmp % i == 0) {
                tmp /= i;
                p[i]++;
            }
        }
        ll ans = 1;
        if(tmp != 1) {
            ans *= 6;
        }
        for(int i = 2; i <= x; i++) {
            if(p[i]) ans *= p[i] * 6;
        }
        printf("%lld\n", ans);
    }

    return 0;
}