结论

如果 p p p和 q q q互质, 那么 p p p和 q q q不能表示的最大正整数是 ( p − 1 ) ( q − 1 ) − 1 (p - 1)(q - 1) - 1 (p−1)(q−1)−1, 也就是 ≥ ( p − 1 ) ( q − 1 ) \ge (p - 1)(q - 1) ≥(p−1)(q−1)的数都能表示

题目

525. 小凯的疑惑
在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int a, b;
	cin >> a >> b;
	
	cout << (LL) (a - 1) * (b - 1) - 1 << "\n";
	return 0;
}

484. 过河
在这里插入图片描述

思路

很简单能想到线性 d p dp dp, f [ i ] f[i] f[i]表示到达该位置踩过的最小石子数量
但是注意到桥的长度是 1 0 9 10 ^ 9 109量级, 但是每次跳的距离是小于等于 10 10 10的, 对于终点来说由上述结论不能表示的最大最小正整数是 ( 9 − 1 ) ∗ ( 10 − 1 ) − 1 = 71 (9 - 1) * (10 - 1) - 1 = 71 (9−1)∗(10−1)−1=71, 也就是 ≥ 72 \ge 72 ≥72的距离都可以跳到, 因此可以将两个距离很远的石子之间的距离放缩为 100 100 100量级是等价的, 由于最多 100 100 100个石子, 时间复杂度降低到 10 × 100 × 100 10 \times 100 \times 100 10×100×100

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110 * 110, INF = 0x3f3f3f3f;

int len;
int s, t, n;
int pos[N], w[N];
int f[N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> len;
	cin >> s >> t >> n;
	for (int i = 1; i <= n; ++i) cin >> pos[i];
	sort(pos + 1, pos + n + 1);

	// 每次只能跳一次
	if (s == t) {
   
		int res = 0;
		for (int i = 1; i <= n; ++i) {
   
			if (pos[i] % s == 0) res++;
		}
		cout << res << "\n";
		return 0;
	}

	// 压缩石头位置
	int last = 0, val = 0;
	for (int i = 1; i <= n; ++i) {
   
		int diff = pos[i] - last;
		if (diff > 100) val += diff - 100;
		last = pos[i];
		pos[i] -= val;
		w[pos[i]] = 1;
	}

	len = pos[n] + 100;
	memset(f, 0x3f, sizeof f);
	f[0] = 0;

	for (int i = 1; i <= len; ++i) {
   
		for (int j = s; j <= t; ++j) {
   
			int k = i - j;
			if (k >= 0) f[i] = min(f[i], f[k] + w[i]);
		}
	}

	int res = INF;
	for (int i = len - t; i <= len; ++i) {
   
		if (i >= 0) res = min(res, f[i]);
	}

	cout << res << "\n";
	return 0;
}