Google Code Jam 2011 Round 1C : C Perfect Harmony

GCJの過去問を見ていて、この問題をまだ解いていないのでチャレンジ。

数列と数値の上限・下限が与えられる。
数列のすべての数値に対し、割り切るか割り切られる値のうち、上限下限の範囲内にあるものをこたえる問題。
たとえば数列が1 2 5 20で、上限下限が8～16なら、解は10。

smallは数値の範囲が10000までなので、上限下限内の全数値に対し、数列と比較すればよい。
largeは数値が10^16までと範囲が広く、数列も10000要素まであるので、全数チェックはできない。

よって解は以下の通り。
まず、数列に1を入れた上でソートしておく。
例えば以下のような数列があるとき、解は*のどこかにある。(先頭は1なのでそれより小さいことはない。)

解が数列の最大値より大きいなら、解は数列全体の最小公倍数の倍数でなければならない。
解が最大値より小さいなら、解は解より小さい数列の最小公倍数の倍数で、かつ解より大きな数列の最大公約数の約数でなければならない。

上記計算を行うため、最初にのLCMとのGCDを各iについて最初に計算しておくとよいです。

各iについて、のLCMとのGCDを求めた後は、GCDをLCMが割り切るか確認し、そしてLCMとGCDの間で、上限下限の間で、かつLCMをで割り切れ、GCDで割り切れる数値を探します。
LCMとGCDは最大10^16倍差がありますが、約数列挙はなのでなんとか実行できます。

以下がコードです。smallの全数チェックコードもコメントアウトで入れてあります。

int N;
vector<long long> F;
long long L,H;
long long LCM[10001],GCD[10001];
const long long MA = (1LL<<60);

#define GCD_TYPE long long
GCD_TYPE gcd(GCD_TYPE a, GCD_TYPE b) {
	if(a<b) return gcd(b,a);
	if(b==0) return a;
	return gcd(b,a%b);
}

long long okok(long long lc,long long gc) {
	long long min=MA;
	if(H<lc) return MA;
	if(gc<L) return MA;
	
	long long tmp=lc;
	long long div = gc/lc;
	//_P("%lld %lld %lld %lld\n",lc,gc,L,H);
	for(long long mult=1;lc*mult*mult<=gc;mult++) {
		tmp = mult*lc;
		if(gc%tmp!=0) continue;
		if(tmp>=L && tmp<=H){
			//_P("%lld\n",tmp);
			return tmp;
		}
		if((gc/lc)%mult==0) {
			tmp = lc*(gc/lc/mult);
			if(tmp>=L && tmp<=H){
				//_P("%lld\n",tmp);
				min=tmp;
			}
		}
	}
	return min;
}


void solve(int _loop) {
	int i,j,k,result,dir,ok,state,fstate,up,x,y,sp,dist1,dist2;
	int wid,hei,mv,mi;
	double br,tb1,tb2,start,end;
	long long res;
	N=GETi();
	scanf("%lld",&L);
	scanf("%lld",&H);
	F.clear();
	FOR(i,N) {
		scanf("%lld",&res);
		F.push_back(res);
	}
	F.push_back(1);
	sort(F.begin(),F.end());
	F.erase(unique(F.begin(),F.end()),F.end());
	N = F.size();
	FOR(i,N) {
	}
	
	//GCD
	FOR(i,N) {
		int j = N-1-i;
		if(j==N-1) GCD[j]=F[j];
		else {
			GCD[j]=gcd(GCD[j+1],F[j]);
		}
	}
	//LCD
	FOR(i,N) {
		if(i==0) LCM[i]=F[i];
		else {
			if(LCM[i-1]>=MA) LCM[i]=MA;
			else {
				long long g = gcd(LCM[i-1],F[i]);
				LCM[i]=LCM[i-1]/g*F[i];
				if(LCM[i]>MA || LCM[i]<LCM[i-1]) LCM[i]=MA;
			}
		}
	}
	res=MA;
	FOR(i,N-1) {
		long long lc=LCM[i];
		long long gc=GCD[i+1];
		if(lc>=MA) continue;
		if(gc%lc!=0) continue;
		
		long long tres = okok(lc,gc);
		if(tres<res) res=tres;
	}
	
	// N-1;
	if(LCM[N-1] <= H) {
		long long l1 = (L+LCM[N-1])/LCM[N-1];
		long long h1 = H/LCM[N-1];
		if(h1>=l1 && l1*LCM[N-1] < res) res=l1*LCM[N-1];
	}
	if(res==MA){ _PE("Case #%d: NO\n",_loop);}
	else{  _PE("Case #%d: %lld\n",_loop,res);}
	
	// small
	/*
	for(res=L;res<=H;res++) {
		int ok=1;
		FOR(i,N) {
			if(F[i]%res != 0 && res%F[i] != 0) {
				ok=0;
				break;
			}
		}
		if(ok==1) {
			_PE("Case #%d: %lld\n",_loop,res);
			return;
		}
	}
	_PE("Case #%d: NO\n",_loop);
	return;
	*/
	
}

少々ややこしい問題ですが、なんとかヒント無しで解けたので良かったです。