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

经典的折磨 经典的乱搞

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int N = 1e7+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int n,q;


struct Node{
	int a,b,s;
	bool operator<(const Node&W)const{
		if(s!=W.s)return s<W.s;
		if(a!=W.a)return a<W.a;
		return b<W.b;
	}
}node[N];

void solve()
{
	int cnt = 0;
	cin>>n;
	for(int i=0;i*i<=n;++i)
	 for(int j=i;j*j+i*i<=n;++j)
	  node[++cnt] = {i,j,i*i+j*j};
	
	sort(node+1,node+1+cnt);

	for(int a=0;a*a<=n;a++)
	 for(int b=0;b*b+a*a<=n;++b)
	  {
	  		int l = 0,r = cnt;
	  		while(l+1!=r){
	  			int mid = (l+r)/2;
	  			if(node[mid].s<n-a*a-b*b)l = mid;
	  			else r = mid;
	  		}

	  		
	  		if(node[r].s==n-a*a-b*b){
	  			cout<<a<<" "<<b<<" "<<node[r].a<<" "<<node[r].b<<"\n";return;
	  		}
	  }
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}