Calculate the Sum of GCD over all subarrays | Utility function to calculate sum of gcd of all sub - arrays . ; Fixing the starting index of a subarray ; Fixing the ending index of a subarray ; Finding the GCD of this subarray ; Adding this GCD in our sum ; Driver Code
def findGCDSum ( n , a ) : NEW_LINE INDENT GCDSum = 0 ; NEW_LINE tempGCD = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i , n ) : NEW_LINE INDENT tempGCD = 0 ; NEW_LINE for k in range ( i , j + 1 ) : NEW_LINE INDENT tempGCD = __gcd ( tempGCD , a [ k ] ) ; NEW_LINE DEDENT GCDSum += tempGCD ; NEW_LINE DEDENT DEDENT return GCDSum ; NEW_LINE DEDENT def __gcd ( a , b ) : NEW_LINE INDENT return a if ( b == 0 ) else __gcd ( b , a % b ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 ; NEW_LINE a = [ 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE totalSum = findGCDSum ( n , a ) ; NEW_LINE print ( totalSum ) ; NEW_LINE DEDENT