FromToDivisible [SRM 699 : Div1 Med]

問題

1～Nの番号がついているグラフがある。
ここでM組のa[i]とb[i]が与えられる。
「XからYへの辺がある」⇔「Xがa[i]の倍数かつYがb[i]の倍数」で辺がある。
このとき、始点Sから始点Tまでの最短距離は？
もし到達不可能なら-1

2 <= N <= 10^9
1 <= M <= 10^3

考察

1. Nがとても大きいので普通のグラフ問題じゃない
2. 一方Mの値が小さいので、Mの方について考えていったほうが良さそう

3. まず、始点Sから始まる時に使えるa[i],b[i]の組について考えると、S/a[i]が割り切れるものがまず使えると分かる
4. ここからが重要で、a[i]->b[i]を使った時に次にa[j]->b[j]が使えるのは、lcm(b[i], a[j]) <= Nのときであるということ
5. これが分かるとこの問題はかなり簡単
6. あとは、T / B[i]が割り切れればB[i]からTへ辺があるため、答えとなる

7. 具体的には、以下のように辺を貼って、コストはどれも1なのでBFS

• S / a[i]が割り切れるとき、Sからb[i]へ辺をはる
• lcm(b[i], a[j]) <= Nを満たすとき、b[i]からb[j]へ辺をはる
• T / b[i]が割り切れるとき、b[i]からTへ辺をはる

実装

typedef long long ll;
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

struct FromToDivisible
{
	int shortest(int N, int S, int T, vector <int> a, vector <int> b)
	{
		int M = a.size();

		set<int> done;
		map<int, int> dist;
		queue<int> que;

		done.insert(S);
		dist[S] = 0;
		rep(i, 0, M) {
			if (S % a[i] == 0) {
				if (N < b[i]) continue;
				done.insert(b[i]);
				dist[b[i]] = 1;
				que.push(b[i]);
			}
		}

		while (!que.empty()) {
			int q = que.front(); que.pop();
			if (T % q == 0) return dist[q];

			rep(i, 0, M) {
				ll _lcm = lcm(q, a[i]);
				if ((ll)N < _lcm) continue;
				if (done.find(b[i]) != done.end()) continue;
				done.insert(b[i]);
				dist[b[i]] = dist[q] + 1;
				que.push(b[i]);
			}
		}

		return -1;
	}
};