GCD and LCM HDU 4497 数论

题意

给你三个数x,y,z的最大公约数G和最小公倍数L，问你三个数字一共有几种可能。注意123和321算两种情况。

解题思路

L代表LCM，G代表GCD。
\[ x=(p_1^{i_1})*(p_2^{i_2})*(p_3^{i_3})\dots \]

\[ y=(p_1^{j_1})*(p_2^{j_2})*(p_3^{j_3})\dots \]

\[ z=(p_1^{k_1})*(p_2^{k_2})*(p_3^{k_3})\dots \]

\[ G=(p_1^{m_1})*(p_2^{m_2})*(p_3^{m_3})\dots \]

\[ L=(p_1^{n_1})*(p_2^{n_2})*(p_3^{n_3})\dots \]

m是i j k 中得最小值，n是i j k中得最大值。

那么L/G得
\[ L/G=(p_1^{r_1})*(p_2^{r_2})*(p_3^{r_3})\dots \]

\[ x/G=(p_1^{a_1})*(p_2^{a_2})*(p_3^{a_3})\dots \]

\[ y/G=(p_1^{b_1})*(p_2^{b_2})*(p_3^{b_3})\dots \]

\[ z/G=(p_1^{c_1})*(p_2^{c_2})*(p_3^{c_3})\dots \]

那么 \(a\) \(b\) \(c\) 中一定有一个是 \(r\) ,也一定有一个是 \(0\) 为什么呢？因为x, y, z 分别处以最大公约数后，指数就相应的减少了，这样就会使得a， b， c，中有一个是0。

这样a，b， c，中就有三种情况。

r， 0， 0， C（3， 1）三种

r， 0， r，C（3， 1）三种

r， 0， 1~r-1 有（r-1）*A（3， 3）

有6*r种，

代码实现

/*15ms,200KB*/
 
#include<cstdio>
 
int main()
{
    int t;
    long long m, n, ans, i, count;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%I64d%I64d", &m, &n);
        if (n % m) puts("0");///注意特判
        else
        {
            n /= m;
            ans = 1;
            for (i = 2; i * i <= n; i += 2)///不用求素数，因为范围很小(注意n在不断减小)
            {
                if (n % i == 0)
                {
                    count = 0;
                    while (n % i == 0)
                    {
                        n /= i;
                        ++count;
                    }
                    ans *= 6 * count;
                }
                if (i == 2)
                    --i;///小技巧
            }
            if (n > 1) ans *= 6;
            printf("%I64d\n", ans);
        }
    }
    return 0;
}