Sum of GCD of all possible sequences | JavaScript implementation of the above approach ; Function to find a ^ b in log ( b ) ; Function that finds the sum of GCD of all the subsequence of N length ; To stores the number of sequences with gcd i ; Find contribution of each gcd to happen ; To count multiples ; possible sequences with overcounting ; to avoid overflow ; Find extra element which will not form gcd = i ; Find overcounting ; Remove the overcounting ; To store the final answer ; Return Final answer ; Driver Code ; Function call
var MOD = 1000000007 ; function fastexpo ( a , b ) { var res = 1 ; a %= MOD ; while ( b ) { if ( b & 1 ) res = ( res * a ) % MOD ; a *= a ; a %= MOD ; b >>= 1 ; } return res ; } function sumofGCD ( n , k ) { var count = Array ( k + 1 ) . fill ( 0 ) ; for ( var g = k ; g >= 1 ; g -- ) { var count_multiples = k / g ; var temp ; temp = fastexpo ( count_multiples , n ) ; temp %= MOD ; var extra = 0 ; for ( var j = g * 2 ; j <= k ; j += g ) { extra = ( extra + count [ j ] ) ; extra %= MOD ; } count [ g ] = ( temp - extra + MOD ) ; count [ g ] %= MOD ; } var sum = 0 ; var add ; for ( var i = 1 ; i <= k ; ++ i ) { add = ( count [ i ] % MOD * i % MOD ) ; add %= MOD ; sum += add ; sum %= MOD ; } return sum ; } var N = 3 , K = 2 ; document . write ( sumofGCD ( N , K ) ) ;