2429-GCD & LCM Inverse

問題（外部リンク）

2429 -- GCD & LCM Inverse

実装の概要

与えられた最大公約数（GCD）と最小公倍数（LCM）からもともとの2つの整数を逆算する問題。
入力値がlong型なので全パターン試そうとすると間に合いません。また、a+bが最小になるようにという条件にも注意が必要です。
そこで、（ただしは互いに素）とすると、と表せることを利用します。するとa,bではなく適切なp,qを探せばよいのでこの時点で探す範囲が1からに限定されます。
そしてこのp,qも1から探していく必要はありません。からpの値を小さくし、条件を満たす（つまりp,qが互いに素な）pとqの組み合わせが見つかればそこで処理を終えても大丈夫です。
理由をざっくりと説明すると、pの値を小さくしてしまうと（もちろんqが整数になるような値にします）qがその分だけ大きくなるだけでは済まず、和が最小という条件を満たすことができないからです。
そしてa<=bという条件からp<=qであり、pとして有り得る値の最大値はp=q、すなわちとなります。
実際、問題ページの例であればまずとなり、なのでp=4から順に検証すれば良いということになります。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			String input = br.readLine();
			
			if(input == null){
				break;
			}
			String[] tmpArray = input.split(" ");

			long gcd = Long.parseLong(tmpArray[0]);
			long lcm = Long.parseLong(tmpArray[1]);
			
			long pq = lcm/gcd;
			
			long p = 0;
			long q = 0;
			for(int i = (int)Math.sqrt(pq) ; i >= 1; i--){
				if(pq%i == 0){
					p = i;
					q = pq/i;
					
					//互いに素であるかチェック
					if(GCD(p, q)== 1){
						break;
					}
				}
			}
			
			System.out.println(p*gcd+" "+q*gcd);
		}
	}
	
    static long GCD (long a, long b){
	    long c = a;
	    while (b % a != 0) {
	      c = b % a;
	      b = a;
	      a = c;
	    }
	    return c;
	}

}