SRM 535 250pt FoxAndGCDLCM

ちょっと古い問題をいまさら考える

問題

最大公約数と最小公倍数が与えられ、aとbが与えられた最大公約数、最小公倍数である和の最小値を求める。

javaのコード

public class FoxAndGCDLCM {
	public long gcd(long b, long s){
		if(s==0)
			return b;
		return gcd(s,b%s);
	}
	public long lcm(long b, long s){
		return b*s/gcd(b,s);
	}
	public long get2(long G, long L) {
		long ret=Long.MAX_VALUE;
		for(long a=G;a<=L;a+=G){
			long b=G*L/a;
			if(G==gcd(b,a) && L==lcm(b,a)){
				ret=Math.min(ret, a+b);
			}
		}
		if(ret!=Long.MAX_VALUE)
			return ret;
		else
			return -1;
	}
	
	public long get(long G, long L) {
		if(L%G!=0)
			return -1;
		long newG=G/G,newL=L/G;
		long ret=Long.MAX_VALUE;
		for(long a=newG;a*a<=newL;a+=newG){
			long b=newG*newL/a;
			if(newG==gcd(b,a) && newL==lcm(b,a)){
				ret=Math.min(ret, a+b);
			}
		}
		if(ret!=Long.MAX_VALUE)
			return G*ret;
		else
			return -1;
	}
}

解説

gcdとlcmの他に2つメソッドがあって、getは正解でget2は不正解になっている。
get2は時間が足りず不正解なのだけど、get2をすぐにつくって「どうやって計算量おとすかなー」って問題だと思う。

よく見るとgetとget2はかなり似ているのだけど、どこが違うのか注目する。

getはnewGとnewLという新しい最大公約数と最小公倍数を設定している。それは元の最大公約数と最小公倍数の両方を、最大公約数で割ったものになっている。
新しい公約数と公倍数で答えを求めて、後で最初の割った最大公約数を掛けることで元の公約数、公倍数の答えになる。
この新しい最大公約数と最小公倍数を設定するためには、前提知識として

  • 最小公倍数は最大公約数の倍数

であることを知っている必要がある。
これによって、オーバーフローしなくなるとかメリットはあると思うのだけど、これだけじゃ計算量は落ちない。

新しい最大公約数は必ず1になることによって計算量を落とすことができる。
候補となるaとbを全通り調べるのだけど、getとget2共に最大公約数の倍数であり最小公倍数の約数をaにしている。
この時、最大公約数が1の場合、素数判定とほぼ同じアルゴリズムになる。
素数判定はxが素数か調べる時、2〜√xで割れなければ素数であることが分かる。
この2〜√xまで調べれば良いことが分かっていないといけないのだけど、

for(long a=newG;a*a<=newL;a+=newG)

とすることで√xまで計算量を落とすことができる。

上のコードでは分かりやすくするためにnewGを用意しているけどnewGは必ず1になるので、この変数をなくして簡略化したものがTopCoderでみれるソースになっている。

蛇足

素数判定の高速化について√xではなくx/2の方が分かりやすいのだけど、xが大きくなってくると全然違ってくる。
xが1億だとすると、√x=1万、x/2=5000万で、√xの方が5000倍速い