Filling the prefix array following relation prefix ( i ) = __gcd ( prefix ( i - 1 ) , arr ( i ) )
prefix [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) prefix [ i ] = __gcd ( prefix [ i - 1 ] , arr [ i ] ) ;