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;

}

巴特西

GCD and LCM HDU 4497 数论

GCD and LCM HDU 4497 数论

题意

解题思路

代码实现

最新文章

热门文章