Generate an N | Function to calculate GCD of given array ; Function to calculate GCD of two integers ; Utility function to check for all the combinations ; If a sequence of size N is obtained ; If gcd of current combination is K ; If current element from first array is divisible by K ; Recursively proceed further ; If current combination satisfies given condition ; Remove the element from the combination ; If current element from second array is divisible by K ; Recursively proceed further ; If current combination satisfies given condition ; Remove the element from the combination ; Function to check for all possible combinations ; Stores the subsequence ; If GCD of any sequence is not equal to K ; Given arrays ; Given value of K ; Function call to generate a subsequence whose GCD is K
def GCDArr ( a ) : NEW_LINE INDENT ans = a [ 0 ] NEW_LINE for i in a : NEW_LINE INDENT ans = GCD ( ans , i ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def GCD ( a , b ) : NEW_LINE INDENT if not b : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT def findSubseqUtil ( a , b , ans , k , i ) : NEW_LINE INDENT if len ( ans ) == len ( a ) : NEW_LINE INDENT if GCDArr ( ans ) == k : NEW_LINE INDENT print ( ans ) NEW_LINE return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if not a [ i ] % K : NEW_LINE INDENT ans . append ( a [ i ] ) NEW_LINE temp = findSubseqUtil ( a , b , ans , k , i + 1 ) NEW_LINE if temp == True : NEW_LINE INDENT return True NEW_LINE DEDENT ans . pop ( ) NEW_LINE DEDENT if not b [ i ] % k : NEW_LINE INDENT ans . append ( b [ i ] ) NEW_LINE temp = findSubseqUtil ( a , b , ans , k , i + 1 ) NEW_LINE if temp == True : NEW_LINE INDENT return True NEW_LINE DEDENT ans . pop ( ) NEW_LINE DEDENT return False NEW_LINE DEDENT def findSubseq ( A , B , K , i ) : NEW_LINE INDENT ans = [ ] NEW_LINE findSubseqUtil ( A , B , ans , K , i ) NEW_LINE if not ans : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT DEDENT A = [ 5 , 3 , 6 , 2 , 9 ] NEW_LINE B = [ 21 , 7 , 14 , 12 , 28 ] NEW_LINE K = 3 NEW_LINE ans = findSubseq ( A , B , K , 0 ) NEW_LINE