3626 三元一次方程（枚举）

方程（枚举）"/>

3626 三元一次方程（枚举）

1. 问题描述：

给定一个整数 n，请你求出三元一次方程 3x + 5y + 7z = n 的一组非负整数解。要求：

x ≥ 0，y ≥ 0，z ≥ 0
如果解不唯一，则输出 x，y，z 字典序最小的解。

输入格式

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

输出格式

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

数据范围

对于前三个测试点，1 ≤ n ≤ 100。
对于全部测试点，1 ≤ T ≤ 1000，1 ≤ n ≤ 1000。

输入样例：

4
30
67
4
14

输出样例：

0 6 0
0 5 6
-1
0 0 2
来源：/

2. 思路分析：

分析题目可以知道x，y，z中最大的数为n // 3，而且n最大是1000，所以可以暴力枚举x和y的值，对于z我们可以判断n - 3x - 5y是否是7的倍数，并且n >= 3x + 5y，如果满足这两个条件说明满足当前枚举的x，y和z满足方程大于等于0的整数解的要求。

3. 代码如下：

class Solution:# 求解当前等于n的x, y, z的解def work(self, n):x = 0while x * 3 <= n:y = 0while x * 3 + y * 5 <= n:if (n - 3 * x - 5 * y) % 7 == 0:print(x, y, (n - 3 * x - 5 * y) // 7)return Truey += 1x += 1return Falsedef process(self):T = int(input())for i in range(T):n = int(input())if not self.work(n):print(-1)if __name__ == '__main__':Solution().process()