Fake_Solution
前言
[warning]: 本题解的做法是错法，但是正确概率贼高。离谱的是正确率还可以叠加。
正解是记搜，时间复杂度可以证明。正解看文末。
思考
众所周知一个公式：
\[a\times b=\operatorname{lcm}(a,b)\times \gcd(a,b) \]如果你不知道——自证吧，不难。
于是，移一下项可得
\[\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)} \]那本题就是求这个玩意儿（设 \(g(a,b)=\gcd(a,b)\)， \(g(X)=g(x_1,\dots,x_n)\)）
\[\frac{g(X)\times g(Y)}{g(g(X),g(Y))} \]关键是，我们怎么求得这个分数呢？
观察一手分母，实际上就是
\[g(g(x_1,\dots,x_m),g(x_1,\dots,x_m))\\\Downarrow\\g(x_1,\dots,x_m,y_1,\dots,y_m)\\\Downarrow\\g(a_1,\dots,a_n) \]也就是说无论怎么放置卡片，分母是始终不变的。都可以根据给出的值求得。
分子怎么办呢？
由于是 \(g(X)\times g(Y)\)，我们可以试着贪心去取较大值。然后一路 \(O(n)\) 下去就好了。
但是会有问题（极小概率），给个 hack。
3
7175 27378
9184 26427
29992 7190
但是，数据出现这种卡贪心的情况概率极低。Atcoder 的 70 组数据也就一组。
为了提高正确率，我们可以倒着再跑一次。
是的，你没听错，就是贪心 + 乱搞。
代码
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 50 + 5;
int n;
int a[MAXN], b[MAXN];
int solve() {
int x = a[1], y = b[1];
for (int i = 2; i <= n; i++) {
int nx = __gcd(x, a[i]);
int ny = __gcd(y, b[i]);
int mx = __gcd(x, b[i]);
int my = __gcd(y, a[i]);
if (nx * ny > mx * my)
x = nx, y = ny;
else
x = mx, y = my;
}
return x * y / gcd(x, y);
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
int ans1 = solve();
for (int i = 1, j = n; i <= j; i++, j--) swap(a[i], a[j]), swap(b[i], b[j]);
int ans2 = solve();
printf("%lld\n", max(ans1, ans2));
return 0;
}
Solution
还是补一个正解做法。其实直接记忆化爆搜就好了，时间复杂度可以证明通过本题限制（虽然我不会）。
代码
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 50 + 5;
int n;
int a[MAXN], b[MAXN];
struct node {
int x, ga, gb;
node(int a = 0, int b = 0, int c = 0) {
x = a;
ga = b;
gb = c;
}
bool operator<(const node &T) const {
if (x != T.x)
return x < T.x;
if (ga != T.ga)
return ga < T.ga;
return gb < T.gb;
}
};
int ans;
map<node, bool> vis;
int lcm(int a, int b) { return a * b / __gcd(a, b); }
void dfs(int x, int ga, int gb) {
if (vis[node(x, ga, gb)])
return;
vis[node(x, ga, gb)] = 1;
if (x == n + 1) {
ans = max(ans, lcm(ga, gb));
return;
}
dfs(x + 1, __gcd(ga, a[x]), __gcd(gb, b[x]));
dfs(x + 1, __gcd(ga, b[x]), __gcd(gb, a[x]));
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
dfs(2, a[1], b[1]);
printf("%lld\n", ans);
return 0;
}