Products of ranges in an array | Returns modulo inverse of a with respect to m using extended Euclid Algorithm . Assumption : a and m are coprimes , i . e . , gcd ( a , m ) = 1 ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Make x1 positive ; calculating pre_product array ; Cacluating inverse_product array . ; Function to calculate Product in the given range . ; As our array is 0 based as and L and R are given as 1 based index . ; Driver Code ; Array ; Prime P ; Calculating PreProduct and InverseProduct ; Range [ L , R ] in 1 base index
def modInverse ( a , m ) : NEW_LINE INDENT m0 , x0 , x1 = m , 0 , 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 = a % m , 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 calculate_Pre_Product ( A , N , P ) : NEW_LINE INDENT pre_product [ 0 ] = A [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT pre_product [ i ] = pre_product [ i - 1 ] * A [ i ] NEW_LINE pre_product [ i ] = pre_product [ i ] % P NEW_LINE DEDENT DEDENT def calculate_inverse_product ( A , N , P ) : NEW_LINE INDENT inverse_product [ 0 ] = modInverse ( pre_product [ 0 ] , P ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT inverse_product [ i ] = modInverse ( pre_product [ i ] , P ) NEW_LINE DEDENT DEDENT def calculateProduct ( A , L , R , P ) : NEW_LINE INDENT L = L - 1 NEW_LINE R = R - 1 NEW_LINE ans = 0 NEW_LINE if L == 0 : NEW_LINE INDENT ans = pre_product [ R ] NEW_LINE DEDENT else : NEW_LINE INDENT ans = pre_product [ R ] * inverse_product [ L - 1 ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE N = len ( A ) NEW_LINE P = 113 NEW_LINE MAX = 100 NEW_LINE pre_product = [ None ] * ( MAX ) NEW_LINE inverse_product = [ None ] * ( MAX ) NEW_LINE calculate_Pre_Product ( A , N , P ) NEW_LINE calculate_inverse_product ( A , N , P ) NEW_LINE L , R = 2 , 5 NEW_LINE print ( calculateProduct ( A , L , R , P ) ) NEW_LINE L , R = 1 , 3 NEW_LINE print ( calculateProduct ( A , L , R , P ) ) NEW_LINE DEDENT