GCDGraph TopCoder グラフに置ける2点間に経路があるか否か

問題URL

arena.topcoder.com

Problem Statement

You are given four s: n, k, x, and y.

The s n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and only if gcd(i, j) > k. Here, gcd(i, j) denotes the greatest common divisor of i and j.

The s x and y are the numbers of two (not necessarily distinct) vertices in our graph. Return "Possible" if it is possible to travel from x to y by following the edges of our graph. Otherwise, return "Impossible".

In other words, return "Possible" if our graph contains a path that connects the nodes x and y, and "Impossible" if there is no such path.

Definition

Class: GCDGraph Method: possible Parameters: int, int, int, int Returns: String Method signature: String possible(int n, int k, int x, int y) (be sure your method is public)

Constraints

  • n will be between 2 and 1,000,000, inclusive.
  • k will be between 0 and n, inclusive.
  • x and y will be between 1 and n, inclusive.

要約

N個のノードが与えられ、それぞれのノードには整数i(1 <= i <= N)が振られている。頂点i, jにおいて、i, jの最大公約数がkより大きければi, j間を繋げる。このようにして作成されるグラフにおいて、与えられる頂点x, y間には経路が存在するか否かという問題。

解法

「与えられた2点間x, yに経路が存在するか」という問いは「xのルートノードとyのルートノードは一致するか」という問に変更できる。経路が存在するとうことは2つの頂点は同じグラフに属しているからだ。これを高速に算出するためにUnion-Findという手法を用いる。

Union-Findとは

Union-Findとは、結合(Union)とルートノードを探す(Find)の2つの操作を用いて、任意のノードのルートノードを取得するためのアルゴリズムである。これを応用して2つのノードが同じグラフに属しているかを判定することができる。

詳しくは以下を参照。

keita-matsushita.hatenablog.com

最大公約数を工夫して算出する

全ての頂点i, jに対して最大公約数を求めようとするとNが最大106なので間に合わない。そこで以下のような手段を取る。

詳しく見てみる。最大公約数を固定しgcdと名付ける。gcdの倍数を「i」と名付けた時に、gcdとiの最大公約数は必ずgcdとなる。 つまり、gcdとi間は必ず経路が存在し辺を渡す事ができる。固定したgcdをK < gcd <= Nまで行うことで、全てのパターンを満たす事ができる。

ソースコード