Calculate the Sum of GCD over all subarrays | Python3 program to find Sum of GCD over all subarrays ;  ; Build Sparse Table ; Building the Sparse Table for GCD [ L , R ] Queries ; Utility Function to calculate GCD in range [ L , R ] ; Calculating where the answer is stored in our Sparse Table ; Utility Function to find next - farther position where gcd is same ; BinarySearch for Next Position for EndPointer ; Utility function to calculate sum of gcd ; Initializing all the values ; Finding the next position for endPointer ; Adding the suitable sum to our answer ; Changing prevEndPointer ; Recalculating tempGCD ; Driver code
from math import gcd as __gcd , log , floor NEW_LINE / * int a [ 100001 ] ; * / NEW_LINE SparseTable = [ [ 0 for i in range ( 51 ) ] for i in range ( 100001 ) ] NEW_LINE def buildSparseTable ( a , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT SparseTable [ i ] [ 0 ] = a [ i ] NEW_LINE DEDENT for j in range ( 1 , 20 ) : NEW_LINE INDENT for i in range ( n - ( 1 << j ) + 1 ) : NEW_LINE INDENT SparseTable [ i ] [ j ] = __gcd ( SparseTable [ i ] [ j - 1 ] , SparseTable [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT def queryForGCD ( L , R ) : NEW_LINE INDENT j = floor ( log ( R - L + 1 , 2 ) ) NEW_LINE returnValue = __gcd ( SparseTable [ L ] [ j ] , SparseTable [ R - ( 1 << j ) + 1 ] [ j ] ) NEW_LINE return returnValue NEW_LINE DEDENT def nextPosition ( tempGCD , startPointer , prevEndPointer , n ) : NEW_LINE INDENT high = n - 1 NEW_LINE low = prevEndPointer NEW_LINE mid = prevEndPointer NEW_LINE nextPos = prevEndPointer NEW_LINE while ( high >= low ) : NEW_LINE INDENT mid = ( ( high + low ) >> 1 ) NEW_LINE if ( queryForGCD ( startPointer , mid ) == tempGCD ) : NEW_LINE INDENT nextPos = mid NEW_LINE low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return nextPos + 1 NEW_LINE DEDENT def calculateSum ( a , n ) : NEW_LINE INDENT buildSparseTable ( a , n ) NEW_LINE tempAns = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT endPointer = i NEW_LINE startPointer = i NEW_LINE prevEndPointer = i NEW_LINE tempGCD = a [ i ] NEW_LINE while ( endPointer < n ) : NEW_LINE INDENT endPointer = nextPosition ( tempGCD , startPointer , prevEndPointer , n ) NEW_LINE tempAns += ( ( endPointer - prevEndPointer ) * tempGCD ) NEW_LINE prevEndPointer = endPointer NEW_LINE if ( endPointer < n ) : NEW_LINE INDENT tempGCD = __gcd ( tempGCD , a [ endPointer ] ) NEW_LINE DEDENT DEDENT DEDENT return tempAns NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 6 NEW_LINE a = [ 2 , 2 , 2 , 3 , 5 , 5 ] NEW_LINE print ( calculateSum ( a , n ) ) NEW_LINE DEDENT