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 astatic void overflow ; Return the readonly 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
using System ; public class GFG { static int MOD = ( int ) 1e9 + 7 ; static 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 ; } static int sumofGCD ( int n , int k ) { return calculate ( 0 , 0 , n , k ) ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void Main ( String [ ] args ) { int N = 3 , K = 2 ; Console . Write ( sumofGCD ( N , K ) ) ; } }