Calculate the Sum of GCD over all subarrays | int a [ 100001 ] ; ; 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
let SparseTable = new Array ( 100001 ) ; for ( let i = 0 ; i < 100001 ; i ++ ) { SparseTable [ i ] = new Array ( 51 ) ; for ( let j = 0 ; j < 51 ; j ++ ) { SparseTable [ i ] [ j ] = 0 ; } } function buildSparseTable ( a , n ) { for ( let i = 0 ; i < n ; i ++ ) { SparseTable [ i ] [ 0 ] = a [ i ] ; } for ( let j = 1 ; j <= 19 ; j ++ ) { for ( let i = 0 ; i <= n - ( 1 << j ) ; i ++ ) { SparseTable [ i ] [ j ] = __gcd ( SparseTable [ i ] [ j - 1 ] , SparseTable [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ) ; } } } function queryForGCD ( L , R ) { let returnValue ; let j = Math . floor ( Math . log ( R - L + 1 ) ) ; returnValue = __gcd ( SparseTable [ L ] [ j ] , SparseTable [ R - ( 1 << j ) + 1 ] [ j ] ) ; return returnValue ; } function nextPosition ( tempGCD , startPointer , prevEndPointer , n ) { let high = n - 1 ; let low = prevEndPointer ; let mid = prevEndPointer ; let nextPos = prevEndPointer ; while ( high >= low ) { mid = ( ( high + low ) >> 1 ) ; if ( queryForGCD ( startPointer , mid ) == tempGCD ) { nextPos = mid ; low = mid + 1 ; } else { high = mid - 1 ; } } return nextPos + 1 ; } function calculateSum ( a , n ) { buildSparseTable ( a , n ) ; let endPointer , startPointer , prevEndPointer , tempGCD ; let tempAns = 0 ; for ( let i = 0 ; i < n ; i ++ ) { endPointer = i ; startPointer = i ; prevEndPointer = i ; tempGCD = a [ i ] ; while ( endPointer < n ) { endPointer = nextPosition ( tempGCD , startPointer , prevEndPointer , n ) ; tempAns += ( ( endPointer - prevEndPointer ) * tempGCD ) ; prevEndPointer = endPointer ; if ( endPointer < n ) { tempGCD = __gcd ( tempGCD , a [ endPointer ] ) ; } } } return tempAns ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } let n = 6 ; let a = [ 2 , 2 , 2 , 3 , 5 , 5 ] ; document . write ( calculateSum ( a , n ) ) ;