题解：P2436 钦定

纯暴力就能过的水题。

1. 解题思路

一眼望过去，不就是取模的运算吗？我们可以枚举循环的周期

k

，然后去计算神犇中对

k

取模中最大的，计算蒟蒻中对

k

取模最小的。这里为了方便，我们把取模的余数设定为

1

至

k

。

令神犇中对

k

取模中最大的为

p

，蒟蒻中对

k

取模最小的为

q

，则需要判断

p

与

q

的关系是否符合条件，及判断

p

是否小于

q

。如果搜到了一个符合要求的

p

和

q

，我们为了满足循环的周期为

k

，再把

q

设置成

k-p

。最后我们再枚举循环周期时发现一个可以的

p

和

q

就与一个 pair<int, int> 类型的答案去最小值即可。

可以用 pair<int, int> 是因为这个类型重载的小于号是先比较 first，再比较 second，刚好符合题目的要求。

2. 代码实现

就知道你们想要这个，专门删掉了注释。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 1010;
constexpr int inf = 0x7fffffff;
int n, m, a[maxn], b[maxn];
signed main(signed argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    while (cin >> n >> m) {
    	pair<int, int> ans = {inf, inf};
    	for (int i = 1; i <= n; i++) cin >> a[i];
    	for (int i = 1; i <= m; i++) cin >> b[i];
    	int x = inf, y = inf;
    	bool flg = false;
    	for (int i = 1; i <= (n + m) * 10; i++) {
    		int xx = -inf, yy = inf;
    		for (int j = 1; j <= n; j++) xx = max(xx, a[j] % i ? a[j] % i : i);
    		for (int j = 1; j <= m; j++) yy = min(yy, b[j] % i ? b[j] % i : i);
    		if (xx >= yy) continue;
    		flg = true;
    		yy = i - xx;
    		ans = min(ans, {xx, yy});
		}
		if (!flg) cout << "NO\n";
		else cout << ans.first << " " << ans.second << "\n";
	}
    return 0;
}

在题解的最后，提前祝大家新年快乐！

题解：P2436 钦定

文章操作

题解：P2436 钦定

1. 解题思路

2. 代码实现

相关推荐

评论

题解：P2436 钦定