SRM 699 Div2 Hard

問題文

TopCoder Statistics - Problem Statement

考察

・であり、の時,]から]に辿ることが出来るということは]と]の最小公倍数になる整数の頂点を通るということ。
・最小公倍数は以下である。

ソースコード

import java.util.*;
public class FromToDivisibleDiv2{
	final int INF = (int)1e9 + 7;
	int M;
	int[] d;
	private class P{
		int first,second;
		public P(int first,int second){
			this.first = first;
			this.second = second;
		}
	}
	public int gcd(int x,int y){
		return y == 0 ? x : gcd(y,x%y);
	}
	public long lcm(int x,int y){
		return (long)x * y / gcd(x,y);
	}
	public int shortest(int N,int S,int T,int[] a,int[] b){
		M = a.length;
		d = new int[M];
		Arrays.fill(d,INF);
		Queue<P> q = new ArrayDeque<P>();
		for(int i = 0;i < M;i++){
			if(S % a[i] == 0){
				q.add(new P(i,1));
				d[i] = 1;
			}
		}
		int ret = -1;
		while(q.size() > 0){
			P p = q.poll();
			if(T % b[p.first] == 0){
				ret = p.second;
				break;
			}
			for(int i = 0;i < M;i++){
				if(d[i] == INF && lcm(b[p.first],a[i]) <= N){
					d[i] = Math.min(d[i],d[p.first] + 1);
					q.add(new P(i,d[i]));
				}
			}
		}
		return ret;
	}
}

本番では解けなかったけど、Hardにしては実装とか考察はそこまで難しくないのかな