Sum of GCD of all possible sequences | C ++ implementation of the above approach ; A recursive function that generates all the sequence and find GCD ; If we reach the sequence of length N g is the GCD of the sequence ; Initialise answer to 0 ; Placing all possible values at this position and recursively find the GCD of the sequence ; Take GCD of GCD calculated uptill now i . e . g with current element ; Take modulo to avoid overflow ; Return the final answer ; Function that finds the sum of GCD of all the subsequence of N length ; Recursive function that generates the sequence and return the GCD ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MOD = ( int ) 1e9 + 7 ; int calculate ( int pos , int g , int n , int k ) { if ( pos == n ) { return g ; } int answer = 0 ; for ( int i = 1 ; i <= k ; i ++ ) { answer = ( answer % MOD + calculate ( pos + 1 , __gcd ( g , i ) , n , k ) % MOD ) ; answer %= MOD ; } return answer ; } int sumofGCD ( int n , int k ) { return calculate ( 0 , 0 , n , k ) ; } int main ( ) { int N = 3 , K = 2 ; cout << sumofGCD ( N , K ) ; return 0 ; }