优化暴力枚举 O(n)
考虑枚举 x 当 x 确定之后
就可以变成 一个 二元一次方程 $$5y + 7z = a - 3x$$
右边是常数, 考虑有无 正整数解
易得(或者通过exgcd 得)
$$y = 3, z = -2$$ 是
$$ 5y + 7z = 1$$ 得解
所以对于任意 $$5y + 7z = k$$
都有 $$ y = 3 * k,
z = -2 * k $$ 是一组解
当获得特解之后 可以获得其的通解是 $$ y = 3 * k + num * 7 (num \in 整数)$$
所以我们希望 $z$ 要是个正整数
那么 $y$ 一定是要越小越好
所以 $y$ 应该取 $3 * k $ % 7 那么此时只需要 看 $z$ 是否是个正整数就行
时间复杂度
O(n)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
typedef long long ll;
int main() {
int t; cin >> t;
while (t--) {
int a; cin >> a;
if (a == 4 || a < 3) {
cout << -1 << endl;
continue;
}
for (int i = 0; i * 3 <= a; ++i) {
ll x = (a - i * 3) * 3 % 7;
ll y = (a - i * 3 - 5 * x) / 7;
if (x >= 0 && y >= 0) {
cout << i << " " << x << " " << y << endl;
break;
}
}
}
}
大佬,请问由特解怎么推到通解的啊
tql
tql
哇,太棒了!!