已知有 \(n\) 个轮子，会有一个车队车来换轮，且恰好使用完这些轮子。只知道这些车中有 \(4\) 轮车和 \(6\) 轮车。你需要估计这个车队最少可能有多少车和最多可能有多少车，或判断这是完全不可能的。
观察：\(4x + 6y = n\) ，由裴蜀定理，当 \(2 \mid n\) 有解且 \(2x + 3y = \frac{n}{2}\) 。
此时问题为 \(2, 3\) 的线性组合，显然易于讨论。不妨让 \(n' = \frac{n}{2}\) 。
显然当 \(2x + 3y = n'\) 有非负整数解，当且仅当 \(n' \geq 2\) 即 \(n \geq 4\) 。
考虑最多车，需要让 \(x\) 尽可能大。
- \(n' \equiv 0 (\mod 2)\) ，\(x = \frac{n'}{2}, y = 0\) 。
- \(n' \equiv 1 (\mod 2)\) ，\(x = \frac{n' - 3}{2}, y = 1\) 。
考虑最少车，需要让 \(y\) 尽可能大。
- \(n' \equiv 0 (\mod 3)\) ，\(y = \frac{n'}{3}, x = 0\) 。
- \(n' \equiv 1 (\mod 3)\) ，\(y = \frac{n' - 4}{3}, x = 2\) 。
- \(n' \equiv 2 (\mod 3)\) ，\(y = \frac{n' - 2}{3}, x= 1\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
ll n; std::cin >> n;
if (n % 2 != 0 || n < 4) std::cout << -1 << '\n';
else {
n /= 2;
ll mi; if (n % 3 == 0) mi = n / 3;
else if (n % 3 == 1) mi = (n - 4) / 3 + 2;
else if (n % 3 == 2) mi = (n - 2) / 3 + 1;
ll mx; if (n % 2 == 0) mx = n / 2;
else if (n % 2 == 1) mx = (n - 2) / 2 + 1;
std::cout << mi << ' ' << mx << '\n';
}
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}
可以将问题扩展，若问题不能化为 \(2, 3\) 的线性组合，将不显然。
若给定 \(n, a, b\) ，再问最小最大值。不妨让 \(a \leq b\) 。
问题即解 \(ax + by = n\) 。
一：若 \(gcd(a, b) \mid n\) ，\(ax + by = n\) 有解。若求出 \(x\) 的最小解，此时 \(y \geq 0\) ，\(ax + by = n\) 有非负整数解。
二：当 \(ax + by = n\) 有非负整数解，\(x\) 最大即 \(y\) 最小时车最多，\(x\) 最小时车最少。
view
#include <bits/stdc++.h>
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
ll _x, _y;
ll d = exgcd(b, a % b, _x, _y);
x = _y;
y = _x - (a / b) * _y;
return d;
}
void solve() {
ll n; std::cin >> n;
ll a = 4, b = 6;
if (a > b) std::swap(a, b);
ll x, y;
ll g = exgcd(a, b, x, y);
if (n % g != 0) std::cout << -1 << '\n';
else {
a /= g; b /= g; n /= g;
if (x < 0) x += b;
x = (x * (n % b)) % b;
y = (n - a * x) / b;
if (y < 0) std::cout << -1 << '\n';
else {
ll mi = x + y;
y = (y * (n % a)) % a;
x = (n - b * y) / a;
ll mx = x + y;
std::cout << mi << ' ' << mx << '\n';
}
}
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}