Sum of GCD of all possible sequences | Java 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 astatic void 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
class GFG { static int MOD = ( int ) 1e9 + 7 ; static int fastexpo ( int a , int b ) { int res = 1 ; a %= MOD ; while ( b > 0 ) { if ( b % 2 == 1 ) res = ( res * a ) % MOD ; a *= a ; a %= MOD ; b >>= 1 ; } return res ; } static int sumofGCD ( int n , int k ) { int [ ] count = new int [ k + 1 ] ; for ( int g = k ; g >= 1 ; g -- ) { int count_multiples = k / g ; int temp ; temp = fastexpo ( count_multiples , n ) ; temp %= MOD ; int extra = 0 ; for ( int j = g * 2 ; j <= k ; j += g ) { extra = ( extra + count [ j ] ) ; extra %= MOD ; } count [ g ] = ( temp - extra + MOD ) ; count [ g ] %= MOD ; } int sum = 0 ; int add ; for ( int i = 1 ; i <= k ; ++ i ) { add = ( count [ i ] % MOD * i % MOD ) ; add %= MOD ; sum += add ; sum %= MOD ; } return sum ; } public static void main ( String [ ] args ) { int N = 3 , K = 2 ; System . out . print ( sumofGCD ( N , K ) ) ; } }