Find a pair ( a , b ) such that Aa + Bb = N | Function to calculate the minimum power of A and B greater than N ; Stores the power of A which is greater than N ; Increment count by 1 ; Divide N by A ; Function to find a pair ( a , b ) such that A ^ a + B ^ b = N ; Calculate the minimum power of A greater than N ; Calculate the minimum power of B greater than N ; Make copy of A and B ; Traverse for every pair ( i , j ) ; Check if B ^ j + A ^ i = N To overcome the overflow problem use B = N - A rather than B + A = N ; Increment power B by 1 ; Increment power A by 1 ; Finally pr - 1 if no pair is found ; Driver Code ; Given A , B and N ; Function Call
def power ( A , N ) : NEW_LINE INDENT count = 0 ; NEW_LINE if ( A == 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT while ( N > 0 ) : NEW_LINE INDENT count += 1 ; NEW_LINE N //= A ; NEW_LINE DEDENT return int ( count ) ; NEW_LINE DEDENT def Pairs ( N , A , B ) : NEW_LINE INDENT powerA , powerB = 0 , 0 ; NEW_LINE powerA = power ( A , N ) ; NEW_LINE powerB = power ( B , N ) ; NEW_LINE intialB = B ; NEW_LINE intialA = A ; NEW_LINE A = 1 ; NEW_LINE for i in range ( powerA + 1 ) : NEW_LINE INDENT B = 1 ; NEW_LINE for j in range ( powerB + 1 ) : NEW_LINE INDENT if ( B == N - A ) : NEW_LINE INDENT print ( i , " ▁ " , j ) ; NEW_LINE return ; NEW_LINE DEDENT B *= intialB ; NEW_LINE DEDENT A *= intialA ; NEW_LINE DEDENT print ( " - 1" ) ; NEW_LINE return ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 106 ; NEW_LINE A = 3 ; NEW_LINE B = 5 ; NEW_LINE Pairs ( N , A , B ) ; NEW_LINE DEDENT