https://codeforces.com/contest/911/problem/C
题目大意
给出 $k_1, k_2, k_3 \ (1 \le k_i \le 1500)$，问是否可以选出一组整数 $x_1, x_2, x_3$ 使得对于任意 $x \ge \max(x_1, x_2, x_3)$ 有整数 $i, j$ 使得 $k_i * j + x_i$ 成立。
简要题解
这题乍一想只要 $k_i$ 都比较大，肯定是无解，但要枚举并证明小的数只有那么多就比较麻烦。
这里考虑先给 $k_i$ 排序。然后分类讨论。
- 如果最小是 $1$ 那么这一个数就够覆盖所有了。
- 如果最小数是 $2$，那么： a. 如果有另一个 $2$ 也足够了。 b. 考虑另外两个数 $> 2$ 其其中存在奇数 $p$，则其至少是 $3$，且因为 $gcd(p, 2) = 1$，则我们一定可以找到某个点 $x$ 被 $2$ 和 $p$ 都覆盖。而 $x$ 前后相邻点一定是没有被覆盖的，则必须有另一个 $2$，这与假设矛盾。 c. 考虑其他两个数 $p, q \ (\ge 4)$ 都是偶数。显然 $p, q$，选与某个 $2$ 覆盖的位置为起点是没有意义的，那我们考虑让这两个点覆盖 $2$ 没有覆盖到的点，于是我们可以通过把 $p, q$ 都除以 $2$ 转化成两个点 $p', q' \ (\ge 2)$ 且要覆盖所有点，这样有且只有解 $p' = q' = 2$。
- 如果最小数是 $3$，那么考虑 a. 存在数 $x$ 不是 $3$ 的倍数，则 $gcd(3, x) = 1$，同上面的 2b 情况，矛盾，无解。 b. 所有数都是 $3$ 的倍数，此时显然 $3, 3, 3$ 为一组解，当第二大数为 $3$ 时，第三数只有 $3$ 一种选择。这里考虑第二数 $p = 3i > 3$。容易发现，被 $3$ 分隔的某些 $2$ 长区间不会被 $p$ 覆盖，从而我们需要另一个数为 $1$ 矛盾。
- 当最小数 $> 3$，任取 $k_1 * k_2 * k_3$ 长的区间，假定其覆盖不重复，则最多覆盖到 $k_2 k_3 + k_1 k_3 + k_1 k_2$ 个点，不妨设 $3 < k_1 \le k_2 \le k_3$，则我们发现 $k_2 k_3 + k_1 k_3 + k_1 k_2 \le 3 k_2 k_3 \le k_1 k_2 k_3$。这样点都是不能被完全覆盖的，因此无解。
复杂度
$T$：$O(1)$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];
sort(a.begin(), a.end());
if (a[0] == 1) {
cout << "YES\n";
return;
}
if (a[0] == 2) {
if (a[1] == 2) {
cout << "YES\n";
return;
}
if (a[1] == 4 && a[2] == 4) {
cout << "YES\n";
return;
}
}
if (a[0] == 3 && a[1] == 3 && a[2] == 3) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Two Cakes - Educational Codeforces Round 35 (Rated for Div. 2)