SRM 535 Div2 500

SRM 535 Div2 500点の問題

内容は、最大公約数(G)と最小公倍数(L)が入力として与えられ、それを満たす2つの数字を足しあわせて最低となる値を返せ(なければ-1)というもの

簡単な例は、最大公約数が2で最小公倍数が20だとしたらそれを満たす組みは{2, 20}と{4,10}があって、4+10=14の方が小さいので答えは14となる

 そして、無理やり書いたのがこのコード 

public class FoxAndGCDLCM {

    public long get(long G, long L) {
        long a,b;
        a = G;
        b = L;
        long min = -1;
        while(a <= b) {
            if (L % a == 0) {
                b = (L / a)  * G;
                if (gcd(a, b) == G) {
                    if (min == -1 || min > a+b ) {
                        min = a+b;
                    }
                }
            } 
            a += G;
        }
    
        return min;
    }
    
    long gcd(long low, long high){ 
        if (low == 0)
            return high;
        return gcd(high%low, low);
    }

}

正直、解き方が全く分からなかった...

数学の出来なさを改めて痛感

ちなみにこのコードはrun system testを通過できない

あまりにも大きい値はタイムアウトしてしまう

解き方が全くわからないなりに少しは考えてみた

例のG=2とL=20を満たす組みである{2,20},{4,10}について考えてみるとする

組みとして出てくる値は、最大公約数が2となるためには当然どちらも2の倍数の必要がある

 次に、最小公倍数が20であるためにはどちらも20を超えてはいけない

単純に総当りで調べようとしたら、どちらの値も2→4→6→...→n×2とずらして各組み合わせのGとLが一致するか調べる方法がある

しかし、GとLの範囲が1~10^12となっていて大きい値だと２秒以内に結果を返すのは不可能である

結果的にタイムアウトしてしまってはいるが、少しでも処理をすくなくする為に、小さい値の方aを基準に１重のループで考えた

{4,10}と{10,4}は同じ扱いなのでaが大きい値bを超えたら繰り返しを終了とする

次に、aがLの約数になるときだけ可能性があるので検査する

ここでbの求め方が分からなかったのだが、{4,10}をじっくりみると20(L) / 4(a) = 5, 5 * 2(G) = 10(b)という関係が偶然にも見えてきた

ただの偶然なのか{2,20}でも試してみると成り立っている

後で知ったのだが、G * L = a * bという関係が成り立つそうだ

先ほどの式からb = L / a * Gでbを求めて、a+bが以前の値より小さければ最小値を更新するようにした

これで上手く行ったかのように思えたが、{a,b}の組みが何故かG,Lを満たしていいない時があるのだ

そこで最大公約数が正しいか判定するようにしている

これで、時間はかかるが一応正しい答えが得られるようにはなった

 このコードは、Lが大きくGが小さい時にステップ数が増えて、更にLが割り切れやすい数だとbや最大公約数を求めるのにもの凄くの時間を必要とするのが分かる

しかし、解決策が思い当たらないので点数が高い人のコードを見て見ることに 

import java.util.*;
public class FoxAndGCDLCM {
    public long get(long G, long L) {
        int answ = 0;
        if (L % G != 0) {
            return -1;
        }
        long least = L / G;
        long minSum = Long.MAX_VALUE;
        long sqrt = (long)Math.pow(least, 0.5);
        for (int i = 1; i<=sqrt; i++) {
            if (least % i == 0) {
                long tmpSum = least / i + i;
                if (minSum > tmpSum && euclid(least/i, i) == 1) {
                    minSum = tmpSum;
                }
            }
        }
 
         return minSum * G;
    }

    public static long euclid(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return euclid(b, a % b);
        }
    }
}

まず、least = L / Gというのは何を表しているのだろうか？...

least / i + iという魔法のような式はなんなのだろうか？...

というか私の書いたコードはアルゴリズムというか、手順を書いただけのものですよね,,,

こういうのってアルゴリズムのパターンをひたすら覚えるのか、数学的知識を身につけるべきなのか...

何より地頭が悪すぎるorz