分析:y^2=n+x^2=>y^2-x^2=n。
(y-x)(y+x)=n。
令k1=y-x;k2=y+x。
则有:y=(k1+k2)/2,,x=y-k1。
枚举n的所有因数k1,k2使得y为整数。则最小的x即为所求。
注意:x不能为0。
#include<iostream>#include<cmath>using namespace std;void Solve(int n){int i,x,y,minx;minx=0x7fffffff;for(i=1;i<=sqrt(n);i++)if(!(n%i)){if(!((i+n/i)&1)){y=(i+n/i)>>1;x=y-i;if(x)minx=minx<x?minx:x;}}if(minx==0x7fffffff)cout<<-1<<endl;elsecout<<minx<<endl;}int main(){int T,n;cin>>T;while(T–){cin>>n;Solve(n);}return 0;}
继续期待我的下一个旅行,拿起背包,