AOJ1106 Factorization of Quadratic Formula

問題リンク Factorization of Quadratic Formula

• 概要

2次方程式の整数係数a, b, cが与えられる。これを因数分解し、(px+q)(rx+s)としたときのp, q, r, sを答えよ。
但し、p, q, r, sは全て整数であること。また、0

• 解法

まず、2次方程式の解の公式の判別式Dを計算します。
D<0ならそもそも解が無いのでImpossibleです。
D=0なら、重解を持ちます。-b/(2*a)が方程式の解になります。
D>0なら、異なる解を2つ持ちます。しかし、因数分解の際に整数のみが現れるようにしたいので、解の公式の√が消えないといけません。つまり、Dが平方数ならばp, q, r, sが存在することになります。解の公式より、p, q, r, sが求まり、必要ならばp, qとr, sを交換します。

• ソース

import java.util.Scanner;

//Factorization of Quadratic Formula
public class AOJ1106 {

	long gcd(long a, long b){
		return b==0?a:gcd(b, a%b);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			if((a|b|c)==0)break;
			double D = b*b-4*a*c;
			if(D<0)System.out.println("Impossible");
			else if(D==0){
				int A = 2*a;
				int B = -b;
				long g = gcd(Math.abs(A), Math.abs(B));
				A/=g;
				B/=g;
				System.out.println(A+" "+(-B)+" "+A+" "+(-B));
			}
			else{
				int k = 1;
				while(k*k<=D){
					if(k*k==D)break;
					k++;
				}
				if(k*k>D){
					System.out.println("Impossible");continue;
				}
				int P = 2*a;
				int Q = -b+k;
				int R = 2*a;
				int S = -b-k;
				long g = gcd(Math.abs(P), Math.abs(Q));
				P/=g;
				Q/=g;
				g = gcd(Math.abs(R), Math.abs(S));
				R/=g;
				S/=g;
				Q=-Q;
				S=-S;
				if(P>R||(P==R&&Q>S))System.out.println(P+" "+Q+" "+R+" "+S);
				else System.out.println(R+" "+S+" "+P+" "+Q);
			}
		}
	}
	
	public static void main(String[] args) {
		new AOJ1106().run();
	}
}