Single state dynamic programming relation for storing gcd of first i elements from the left in Prefix [ i ]
Prefix [ 1 ] = a [ 0 ] NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT Prefix [ i ] = mt . gcd ( Prefix [ i - 1 ] , a [ i - 1 ] ) NEW_LINE DEDENT