Math

実装例(PyPy3):

math.gcd()は、2つの整数の最大公約数を求めるPythonの組み込み関数です。この関数は、入力された2つの整数$a$, $b$の最大公約数を求め、出力するために使用されます。

この問題は比較的単純なので、より高速なアルゴリズムで最大公約数を求めることができます。例えば、ユークリッドの互除法を用いれば、$O(log(min(a,b))$の時間複雑度で最大公約数を求めることができます。このアルゴリズムは競技プログラミングでよく使われるものなので、覚えておくとよいでしょう。