UVA11342 Three-square 题解

Zskioaert1106 · 2024-08-28 16:22:06 · 题解

题目传送门：UVA11342 Three-square

题目大意：有 N 组数据，每次给你一个数 K，如果 K 能被分解成 K=a^2+b^2+c^2 的形式（a,b,c 均为非负整数）则输出字典序最小的 a,b,c，否则输出 -1。

做题过程

首先我非常一眼的写了暴力：

#include<iostream>
using namespace std;
void blss(int n){
    for(int a=0;a*a<=n;a++){
        for(int b=0;b*b<=n-a*a;b++){
            for(int c=0;c*c<=n-a*a-b*b;c++){
                if(a*a+b*b+c*c==n){
                    cout<<a<<' '<<b<<' '<<c;
                    return;
                }
            }//这里两处的枚举只要分别到(n-a^2)和(n-a^2-b^2)即可
        }
    }
    cout<<-1;//若枚举完都没有满足的情况，按要求输出-1
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        blss(n);
        cout<<'\n';
    }
    return 0;
}

这样是朴素的三重循环。然后，T 飞了。

我们想想看，在前两层循环的前提下，每次遍历时第三层循环的 c 已经确定，且结果无非就是：

• 可以达成性质：输出 a,b,c 并结束函数

• 不可以：进行下一次遍历

而这里只要判断所谓的 c——即 \sqrt{n-a^2-b^2} 是否为整数即可。即我们可以只用两层循环。

于是我们写下了如下代码：

#include<iostream>
#include<cmath>
using namespace std;
void blss(int n){
    for(int a=0;a*a<=n;a++){
        for(int b=0;a*a+b*b<=n;b++){
            int c=sqrt(n-a*a-b*b);
            if(c*c==n-a*a-b*b){
                cout<<a<<' '<<b<<' '<<c;
                return;
            }
        }
    }
    cout<<-1;
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        blss(n);
        cout<<'\n';
    }
    return 0;
}

然后，就过了。。