[蓝桥杯 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;
}