Sum of GCD of all possible sequences | Python3 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
MOD = ( int ) ( 1e9 + 7 ) NEW_LINE def fastexpo ( a , b ) : NEW_LINE INDENT res = 1 NEW_LINE a = a % MOD NEW_LINE while ( b > 0 ) : NEW_LINE INDENT if ( ( b & 1 ) != 0 ) : NEW_LINE INDENT res = ( res * a ) % MOD NEW_LINE DEDENT a = a * a NEW_LINE a = a % MOD NEW_LINE b = b >> 1 NEW_LINE DEDENT return res NEW_LINE DEDENT def sumofGCD ( n , k ) : NEW_LINE INDENT count = [ 0 ] * ( k + 1 ) NEW_LINE for g in range ( k , 0 , - 1 ) : NEW_LINE INDENT count_multiples = k // g NEW_LINE temp = fastexpo ( count_multiples , n ) NEW_LINE temp = temp % MOD NEW_LINE extra = 0 NEW_LINE for j in range ( g * 2 , k + 1 , g ) : NEW_LINE INDENT extra = extra + count [ j ] NEW_LINE extra = extra % MOD NEW_LINE DEDENT count [ g ] = temp - extra + MOD NEW_LINE count [ g ] = count [ g ] % MOD NEW_LINE DEDENT Sum = 0 NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT add = count [ i ] % MOD * i % MOD NEW_LINE add = add % MOD NEW_LINE Sum = Sum + add NEW_LINE Sum = Sum % MOD NEW_LINE DEDENT return Sum NEW_LINE DEDENT N , K = 3 , 2 NEW_LINE print ( sumofGCD ( N , K ) ) NEW_LINE