P8635 [蓝桥杯 2016 省 AB] 四平方和 题解

· · 题解

分析

【主体思路】

对于每个 n，我们可以去枚举 a,b,c 的值，因为在 n=a^2+b^2+c^2+d^2 时，d 一定是等于 \sqrt {n-a^2-b^2-c^2} 的。而 a,b,c,d 又都是整数，所以我们只需要看 d 的值是不是整数就行啦。

【边界判断】

因为题目保证 a \le b \le c \le d，所以在枚举 a 时，若 a^2+a^2+a^2+a^2>n，则一定无法再有可能情况了，b,c 同理。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int check(int a,int b,int c,int d){return a*a+b*b+c*c+d*d;}
//求a^2+b^2+c^2+d^2
int main()
{
    cin>>n;
    for(int i=0;;i++)
    {
        if(check(i,i,i,i)>n) break;//边界判断
        for(int j=i;;j++)
        {
            if(check(i,j,j,j)>n) break;
            for(int k=j;;k++)
            {
                if(check(i,j,k,k)>n) break;
                else
                {
                    int s=sqrt(n-check(i,j,k,0));
                    if(check(i,j,k,s)==n) return cout<<i<<" "<<j<<" "<<k<<" "<<s,0; 
                }
            }
        }
    }
}