自动搬运

查看原文

来自洛谷，原作者为

	Scarlet **

搬运于2025-08-24 22:09:27，当前版本为作者最后更新于2019-04-20 22:01:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家好，我出来卖萌了，相信大家这题做的都很开心（

题解

$k=2$时，直接输出两数，易知正确

$k=3$时，考虑到，$(a,b)[a,b]=ab$，那么六个数乘起来就是$(abc)^2$

因为直接计算$(abc)^2$会爆__int128，所以考虑计算$\frac{(a,b)[a,b](a,c)[a,c]}{(b,c)[b,c]}=\frac{a^2bc}{bc}=a^2$，然后就能算出$a$。但是$a^2bc$也会爆 __int128，所以先让ab除掉gcd(ab,bc)，再让ac除掉bc/gcd(ab,bc)，就可以把两边直接相乘了。

到此，我们可以枚举三个gcd和三个lcm分别怎么配对，就能分别计算出$a$,$b$,$c$

$k=4$时，考虑到对应顺序确定的$k=3$问题的答案是确定的，那么只要枚举某三个和另三个怎么配对，再检验一下剩下三个是否正确就行。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
LLL gcd(LLL a, LLL b) { return b ? gcd(b, a % b) : a; }
LLL lcm(LLL a, LLL b) { return a / gcd(a, b) * b; }
LLL div(LLL a, LLL b, LLL c) //a*b/c;
{
	LLL d1 = gcd(a, c), d2 = c / d1;
	return (a / d1) * (b / d2);
}
LLL sqrt(LLL a)
{
	LLL mid, l = 1, r = 1e18;
	for (; l <= r;)
	{
		mid = l + r >> 1;
		if (mid * mid == a)
			return mid;
		else if (mid * mid < a)
			l = mid + 1;
		else
			r = mid - 1;
	}
	return 0;
}
vector<LL> solve3(LLL g1, LLL g2, LLL g3, LLL l1, LLL l2, LLL l3) //solve (a,b)=g1 (a,c)=g2 (b,c)=g3
{
	LLL ab = g1 * l1, ac = g2 * l2, bc = g3 * l3;
	LLL a2 = div(ab, ac, bc), b2 = div(bc, ab, ac), c2 = div(ac, bc, ab);
	LL a = sqrt(a2), b = sqrt(b2), c = sqrt(c2);
	if (a * b * c == 0)
		return {};
	if (gcd(a, b) == g1 && gcd(a, c) == g2 && gcd(b, c) == g3 && lcm(a, b) == l1 && lcm(a, c) == l2 && lcm(b, c) == l3)
		return {a, b, c};
	else
		return {};
}
LL g[10], l[10];
int k, s;
int work()
{
	s = k * (k - 1) / 2;
	for (int i = 1; i <= s; i++)
		cin >> g[i];
	for (int i = 1; i <= s; i++)
		cin >> l[i];
	if (k == 2)
		printf("%lld %lld\n", l[1], g[1]);
	else if (k == 3)
		for (int _ = 6; _--; next_permutation(g + 1, g + 1 + s))
			for (int __ = 6; __--; next_permutation(l + 1, l + 1 + s))
			{
				auto k = solve3(g[1], g[2], g[3], l[1], l[2], l[3]);
				if (k.size() == 0)
					continue;
				else
					return printf("%lld %lld %lld\n", k[0], k[1], k[2]), 0;
			}
	else
		for (int _ = 720; _--; next_permutation(g + 1, g + 1 + s))
			for (int __ = 720; __--; next_permutation(l + 1, l + 1 + s))
			{
				auto k = solve3(g[1], g[2], g[3], l[1], l[2], l[3]), kk = solve3(g[1], g[4], g[5], l[1], l[4], l[5]);
				if (k.size() == 0 || kk.size() == 0)
					continue;
				if (k[0] != kk[0] || k[1] != kk[1])
					continue;
				vector<LL> ans = {k[0], k[1], k[2], kk[2]};
				if (gcd(ans[2], ans[3]) != g[6] || lcm(ans[2], ans[3]) != l[6])
					continue;
				else
					return printf("%lld %lld %lld %lld\n", ans[0], ans[1], ans[2], ans[3]), 0;
			}
}
int main()
{
	int T;
	for (scanf("%d%d", &T, &k); T--;)
		work();
	return 0;
}