math.gcd と np.ufunc.accumulate で累積GCD

AtCoder Beginner Contest 125 - AtCoderで出題されたC - GCD on Blackboardで、累積GCDが必要になったので、組み込みのGCDとnp.ufunc.accumulate で実装しました。gcdを別の関数に置き換えれば、一般に関数を累積的に適用できます。

GCD

GCDはmathに移行中ですが、AtCoderで利用されているPythonのバージョンではmath.gcdが存在しません。fractionsに実装があるので次のようにして両方の差異を埋めます。

def gcd_strategy():
    import math
    import fractions
    return math.gcd if hasattr(math, "gcd") else fractions.gcd


gcd = gcd_strategy()

累積GCD

numpy.frompyfuncを用いると、ufuncをPythonの関数から手軽に作成できます。

gcd_ufunc = np.frompyfunc(gcd, 2, 1)

作成したufuncを用いると、次のように累積GCDを計算できます。

numbers = [24, 18, 12, 4, 7, 2]
cumgcds = gcd_ufunc.accumulate(numbers, dtype=np.object).astype(np.int)
print(cumgcds) # [24  6  6  2  1  1]

accumulateでdtypeの指定を行わない場合、エラーになります。

参考 : python - generalized cumulative functions in NumPy/SciPy? - Stack Overflow

おまけ

itertoolsを用いても同様のことができます。

from itertools import accumulate
import math
import fractions

gcd =  math.gcd if hasattr(math, "gcd") else fractions.gcd
numbers = [24, 18, 12, 4, 7, 2]
cumgcds = accumulate(numbers, gcd)
print(list(cumgcds)) # [24  6  6  2  1  1]