Smallest value of X satisfying the condition X % A [ i ] = B [ i ] for two given arrays | Python3 program for the above approach ; Function to calculate modulo inverse of a w . r . t m using Extended Euclid Algorithm ; Base Case ; Perform extended euclid algorithm ; q is quotient ; m is remainder now , process same as euclid 's algorithm ; If x1 is negative ; Make x1 positive ; Function to implement Chinese Remainder Theorem to find X ; Stores the product of array elements ; Traverse the array ; Update product ; Initialize the result ; Apply the above formula ; Function to calculate the product of all elements of the array a [ ] ; Stores product of all array elements ; Traverse the array ; Return the product ; Function to find the value of X that satisfies the given condition ; Stores the required smallest value using Chinese Remainder Theorem ; Stores the product of all array elements ; The equation is Y + K * M >= P Therefore , calculate K = ceil ( ( P - Y ) / M ) ; So , X = Y + K * M ; Print the resultant value of X ; Driver Code
import math NEW_LINE def inv ( a , m ) : NEW_LINE INDENT m0 = m NEW_LINE x0 = 0 NEW_LINE x1 = 1 NEW_LINE if ( m == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT while ( a > 1 ) : NEW_LINE INDENT q = a // m NEW_LINE t = m NEW_LINE m = a % m NEW_LINE a = t NEW_LINE t = x0 NEW_LINE x0 = x1 - q * x0 NEW_LINE x1 = t NEW_LINE DEDENT if ( x1 < 0 ) : NEW_LINE INDENT x1 += m0 NEW_LINE DEDENT return x1 NEW_LINE DEDENT def findMinX ( A , B , N ) : NEW_LINE INDENT prod = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT prod *= A [ i ] NEW_LINE DEDENT result = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT pp = prod // A [ i ] NEW_LINE result += B [ i ] * inv ( pp , A [ i ] ) * pp NEW_LINE DEDENT return result % prod NEW_LINE DEDENT def product ( a , n ) : NEW_LINE INDENT ans = 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans *= a [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT def findSmallestInteger ( A , B , P , n ) : NEW_LINE INDENT Y = findMinX ( A , B , n ) NEW_LINE M = product ( A , n ) NEW_LINE K = math . ceil ( ( P - Y ) / M ) NEW_LINE X = Y + K * M NEW_LINE print ( X ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 3 , 4 , 5 ] NEW_LINE B = [ 2 , 3 , 1 ] NEW_LINE n = len ( A ) NEW_LINE P = 72 NEW_LINE findSmallestInteger ( A , B , P , n ) NEW_LINE DEDENT