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
", ans);
}
}
return 0;
}