GCD of Reachable Nodes

頂点$i$（$1 \leq i \leq N$）から到達可能な頂点の集合$S_i$について，$S_i$に含まれる頂点に書いてある数の最大公約数を$G_i$とします．

与えられた有向グラフを強連結成分分解したとき，同じ強連結成分に含まれる任意の$2$頂点$u$，$v$について，明らかに$G_u = G_v$が成り立ちます．従って，まず強連結成分ごとにGCDを求め，次に，強連結成分を頂点とみなした有向非巡回グラフについてDFSの帰りがけ順に子頂点の値のGCDを求めていくことで，全ての頂点における$G_i$を，$\mathrm{O}((N+M) \log (A))$で求めることができます．

コード例（C++）