抄袭党请跳到最后

题目描述

给定一个整数 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

算法1

(暴力枚举) $O(n^3/105)$

循环x,y,z,$O(n^3)$
最大是100^3=1e6
有一千组数据
不可以接受

----------

但是，注意一下题目中的
请你求出三元一次方程 3x+5y+7z=n 的$一组非负整数解$
所以，$0<=x<=n/3$,$0<=y<=n/5$,$0<=z<=n/7$
就可以把复杂度从1e9降到9,523,809.52
从而解决了问题。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,t;
void solve()
{
    for(int i=0;i<=t/3;i++)
        for(int j=0;j<=t/5;j++)
            for(int k=0;k<=t/7;k++)
                if(i*3+j*5+k*7==t)
                {
                    cout<<i<<" "<<j<<" "<<k<<endl;
                    return;
                }
    cout<<"-1\n";
}
int main(){
    cin>>n;
    while(n--)
    {
        cin>>t;
        solve();
    }
}