方程"/>

【ACWing】3626. 三元一次方程

题目地址：

/

给定一个整数 n n n，请你求出三元一次方程 3 x + 5 y + 7 z = n 3x+5y+7z=n 3x+5y+7z=n的一组非负整数解。要求：
1、 x ≥ 0 , y ≥ 0 , z ≥ 0 x≥0,y≥0,z≥0 x≥0,y≥0,z≥0
2、如果解不唯一，则输出 x , y , z x,y,z x,y,z字典序最小的解。

输入格式：
第一行包含一个整数 T T T，表示共有 T T T组测试数据。
每组数据占一行，包含一个整数 n n n。

输出格式：
每组数据输出一行结果，如果无解则输出 − 1 −1 −1，否则输出 x , y , z x,y,z x,y,z，整数之间单个空格隔开。

数据范围：
对于前三个测试点， 1 ≤ n ≤ 100 1≤n≤100 1≤n≤100。
对于全部测试点， 1 ≤ T ≤ 1000 1≤T≤1000 1≤T≤1000， 1 ≤ n ≤ 1000 1≤n≤1000 1≤n≤1000。

直接暴力枚举。代码如下：

#include <iostream>
using namespace std;int n, i, j, k;bool work() {for (i = 0; 3 * i <= n; i++)for (j = 0; 3 * i + 5 * j <= n; j++) {k = n - 3 * i - 5 * j;if (k % 7 == 0) return true;}return false;
}int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &n);if (!work()) puts("-1");else printf("%d %d %d\n", i, j, k / 7);}
}

时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间 O ( 1 ) O(1) O(1)。