题解 P5316 【恋恋的数学题】
Scarlet
·
·
题解
大家好，我出来卖萌了，相信大家这题做的都很开心（
题解
---
$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
---
### 代码
```cpp
#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;
}
```