human
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"
Solution in Python:
assistant
#Here is code to products of ranges in an array and the other steps required.
 def modInverse ( a , m ) :
	m0 , x0 , x1 = m , 0 , 1
	if m == 1 :
		return 0
	while a > 1 :
		q = a // m
		t = m
		m , a = a % m , t
		t = x0
		x0 = x1 - q * x0
		x1 = t
	if x1 < 0 :
		x1 += m0
	return x1
def calculate_Pre_Product ( A , N , P ) :
	pre_product [ 0 ] = A [ 0 ]
	for i in range ( 1 , N ) :
		pre_product [ i ] = pre_product [ i - 1 ] * A [ i ]
		pre_product [ i ] = pre_product [ i ] % P
def calculate_inverse_product ( A , N , P ) :
	inverse_product [ 0 ] = modInverse ( pre_product [ 0 ] , P )
	for i in range ( 1 , N ) :
		inverse_product [ i ] = modInverse ( pre_product [ i ] , P )
def calculateProduct ( A , L , R , P ) :
	L = L - 1
	R = R - 1
	ans = 0
	if L == 0 :
		ans = pre_product [ R ]
	else :
		ans = pre_product [ R ] * inverse_product [ L - 1 ]
	return ans
if __name__ == " _ _ main _ _ " :
	A = [ 1 , 2 , 3 , 4 , 5 , 6 ]
	N = len ( A )
	P = 113
	MAX = 100
	pre_product = [ None ] * ( MAX )
	inverse_product = [ None ] * ( MAX )
	calculate_Pre_Product ( A , N , P )
	calculate_inverse_product ( A , N , P )
	L , R = 2 , 5
	print ( calculateProduct ( A , L , R , P ) )
	L , R = 1 , 3
	print ( calculateProduct ( A , L , R , P ) )