Matsushita's Blog

最大公約数

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…

ユークリッドの互除法を用いて最大公約数を高速に算出する

整数a, bの最大公約数を求める。 2つ整数a, bの最大公約数はユークリッドの互除法を用いる事で高速に算出することができる。 ユークリッドの互除法とは ユークリッドの互除法とは 2つの自然数a, b(a >= b)の最大公約数は、a, bの余りをrとした時にbとrの最…