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 ] = __gcd ( Prefix [ i - 1 ] , a [ i - 1 ] ) ; NEW_LINE DEDENT