acwing1221. 四平方和

题目

题解

哈希

#include<iostream>
#include<cstring>
using namespace std;
const int N=5000010;
int n,C[N],D[N];

int main(){
    cin>>n;
    memset(C,-1,sizeof C);
    for(int c=0;c*c<=n;c++)
        for(int d=c;c*c+d*d<=n;d++){
            int s=c*c+d*d;
            if(C[s]==-1){
                C[s]=c,D[s]=d;
            }
        }
    for(int a=0;a*a<=n;a++){
        for(int b=a;a*a+b*b<=n;b++){
            int s=n-a*a-b*b;
            if(C[s]!=-1){
                cout<<a<<" "<<b<<" "<<C[s]<<" "<<D[s]<<endl;
                return 0;
            }
        }
    }
    return 0;
}