コード
import java.util.ArrayDeque;
import java.util.ArrayList;
public class FromToDivisible {
private static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
static long lcm(long a, long b) {
return a * b / gcd(a, b);
}
final int INF = Integer.MAX_VALUE / 2;
public int shortest(int N, int S, int T, int[] a, int[] b) {
int M = a.length;
ArrayList<Integer> cur = new ArrayList<>();
ArrayList<Integer> next = new ArrayList<>();
ArrayDeque<int[]> edges = new ArrayDeque<>();
for (int i = 0; i < M; i++) {
if (S % a[i] == 0 && T % b[i] == 0) return 1;
if (S % a[i] == 0) cur.add(b[i]);
else edges.add(new int[]{a[i], b[i]});
}
for (int d = 2; d <= 1001; d++) {
next.clear();
int s = edges.size();
for (int i = 0; i < s; i++) {
int[] edge = edges.pollFirst();
boolean used = false;
for (int v : cur) {
if (lcm(v, edge[0]) <= N) {
used = true;
if (T % edge[1] == 0) return d;
next.add(edge[1]);
break;
}
}
if (!used) edges.addLast(edge);
}
ArrayList<Integer> tmp = cur;
cur = next;
next = tmp;
}
return -1;
}
}