ARC124C LCM of GCDs

tony102

2021 年 11 月 12 日

1650 次浏览

暂无评论

528字数

题解

[Link](https://atcoder.jp/contests/arc124/tasks/arc124_c)

## Sol

设 $f_{d1, d2}$ 表示集合 $A$ 里面的数的 $\gcd$ 是 $d_1$，同理 $B$ 的为 $d_2$ 时的最大答案。转移即可。

比较无聊的一道题.....

## Idea

1. 即使数论只会 $\gcd$，也先想想乱搞别的。
2. 发现 `__gcd()` 的实现是 `while` 再每次交换的，时间更优。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair < int, int > PII;
const int SIZE = 55;

int n;
int a[SIZE], b[SIZE];
map < PII, int > f;

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int lcm(int a, int b) { return a / __gcd(b, a % b) * b; }

int dp(int x, int d1, int d2) {
    PII cur = {d1, d2};
    if (f[cur]) return f[cur];
    if (x > n) return lcm(d1, d2);
    int ans = max(dp(x + 1, __gcd(d1, a[x]), __gcd(d2, b[x])), dp(x + 1, __gcd(d1, b[x]), __gcd(d2, a[x])));
    return f[cur] = ans;
}

signed main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 1; i <= n; ++ i) a[i] = read(), b[i] = read();
    printf("%lld\n", dp(1, 0, 0));
    return 0;
}
```

最后修改：2024 年 04 月 09 日