Calculate the Sum of GCD over all subarrays | C # program to find 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
using System ; class GFG { static int [ , ] SparseTable = new int [ 100001 , 51 ] ; static void buildSparseTable ( int [ ] a , int n ) { for ( int i = 0 ; i < n ; i ++ ) { SparseTable [ i , 0 ] = a [ i ] ; } for ( int j = 1 ; j <= 19 ; j ++ ) { for ( int i = 0 ; i <= n - ( 1 << j ) ; i ++ ) { SparseTable [ i , j ] = __gcd ( SparseTable [ i , j - 1 ] , SparseTable [ i + ( 1 << ( j - 1 ) ) , j - 1 ] ) ; } } } static int queryForGCD ( int L , int R ) { int returnValue ; int j = ( int ) ( Math . Log ( R - L + 1 ) ) ; returnValue = __gcd ( SparseTable [ L , j ] , SparseTable [ R - ( 1 << j ) + 1 , j ] ) ; return returnValue ; } static int nextPosition ( int tempGCD , int startPointer , int prevEndPointer , int n ) { int high = n - 1 ; int low = prevEndPointer ; int mid = prevEndPointer ; int 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 ; } static int calculateSum ( int [ ] a , int n ) { buildSparseTable ( a , n ) ; int endPointer , startPointer , prevEndPointer , tempGCD ; int tempAns = 0 ; for ( int 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 ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void Main ( String [ ] args ) { int n = 6 ; int [ ] a = { 2 , 2 , 2 , 3 , 5 , 5 } ; Console . WriteLine ( calculateSum ( a , n ) ) ; } }