yukicoder : No.550 夏休みの思い出（１）

やっぱりここら辺弱いな。
https://yukicoder.me/problems/no/550

問題

３次方程式が与えられる。
係数A,B,Cの絶対値は10^18未満である。
また、この方程式は(-10^9,10^9)の範囲で異なる整数解３つを持つ。

その解を答えよ。

解法

カルダノの公式を使って解くことができるかもしれないが、精度など不安もあるので別解で。

解をp,q,rと置くとpqr=-Cであることから、pqrのうち一つは絶対値が10^6以下である。
よってまずその解を総当たりしよう。

一つ解が求まれば２次方程式に持ち込めるのであとは解の公式で解く。
以下は誤差が怖いのでちょっと周辺も解を探した。
また、途中double型で誤差によりチャレンジを食らったので、long doubleにした。

ll A,B,C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C;
	ll X,Y,Z;
	for(X=-1000000;X<=1000000;X++) {
		if((__int128_t)X*X*X+(__int128_t)A*X*X+(__int128_t)B*X+C==0) {
			break;
		}
	}
	if(X==0) {
		C=B;
		B=A;
	}
	else {
		B=A+X;
		C=-C/X;
	}
	
	long double D=max((long double)0.0,(long double)B*B-4*C);
	for(Y=(-B+sqrt(D))/2-2;Y<=(-B+sqrt(D))/2+2;Y++) {
		
		Z=-B-Y;
		if(abs(Y)>=1000000000) continue;
		if(abs(Z)>=1000000000) continue;
		if(Y*Z!=C) continue;
		if(Y+Z!=-B) continue;
		break;
	}
	
	
	if(X>Y) swap(X,Y);
	if(Y>Z) swap(Y,Z);
	if(X>Y) swap(X,Y);
	cout<<X<<" "<<Y<<" "<<Z<<endl;
	
}

まとめ

誤差が出る問題が怖いので無駄に周辺も探索してしまう。