that thing is ok but when u do that portion prefixModProduct®/prefixModProduct(L-1). here if any element in an array comes zero let suppose 3 element then after that element all subarrays elements product should be zero in our PREFIX PRODUCT ARRAY and then this thing will not work plzz clear this
Suppose we have small values of A[i], so that there’s no risk of overflow. That is… A[0]*A[1]*A[2] … A[N-1] <= 1e18.
In this problem, we can make a prefix product array of given array, and For [l,r] query, answer will be (prefixProd[r]/PrefixProd[l-1]).
But for larger values of A[i], we will face overflow problem, so i stored prefix modular product.
But now, we cannot perform the divide part. Consider following array:
1 2 3 4 5 6 and P = 113
Prefix modular product array will be 1 2 6 24 7 42. Right?
1 Like
So we use modular multiplicative inverse, as explained at wikipedia and geeksforgeeks (links above).
Using this concept (a/b)mod P = (a*inv(B))modP.
So now, we can maintain prefix Modular product and inverse of prefix Modular product, to answer all queries of subtask 1 in O(1) time.
Answer of query (l,r) being (prefixModProduct[r]*inversePrefixModProduct[l-1]) mod P.
Hope that clarifies.
1 Like
plzz check here where i am doing wrong https://ideone.com/PIxj0c ignore the upper headers and commented portion plzz
hey in your above logic ModInverse(L-1) here i have to pass arguments to the function Modinverse(premoduloproduct[L-1],p) like this !
We are precalculating all ModInverses.
No, For calculation of ModInverse,
modInv[i] = exp(premoduloproduct[i], P-2, P).
exp is modular exponentation function, returning (a^b)%P.
1 Like
thnkss bro i have understood we have to use modular exponentiation here but where is the concept of extended euclideans algo comes here for calculation of MMI of prefixmodproduct[Li-1] under modulo p
can u plzz explain this thing breifly i ma not getting it
CREATION OF AN FACT POW SUM ARRAY
factor 0 1 2 3 4 5 6 7 8 9 10 11
2… 0 0 1 1 3 3 4 4 7 7 8 8 (dots to adjust position, spaces are truncated automatically)
3… 0 0 0 1 1 1 2 2 2 4 4 4
And we will think(it’s necessary) we are given given array 1 1 1 1 5 1 7 1 1 5 11 (all numbers are divided by 2 and 3). Now, you will see that all numbers are co-prime to 6.
factPowSum{factorIndex}{i} = factPowSum{factorIndex}{i-1} + Power of factor divided from ith number(1-based indexing).
*
When P is prime, MMI of A can be computed as (A^(P-2)) mod P. This is called fermat’s little theorem. When P is not prime, we have to use extended gcd algorithm to find MMI.
1 Like
ya i just confused in them gcd(a,p) have to be 1 in both cases ok … 
plzz can u clear my doubt in factpowsum portion by taking an small example u say
factpowsum[factorindex][2]=factpowsum[factorindex][1]+power of factor divided from ith number(1 based -indexing)
But later than when u solve this in editorial
** For example, from 8, 3rd pow of 2 was divided, factorPowSum{0}{3} = factorPowSum{0}{4} + 3.
Hope i made the array clear. **
i just cant see where have u used the above stated condition and how ??
I guess you wrote the example wrong.
If 4th term is 8, factPowSum[0][4] = factPowSum[3] + 3.
This way, when we have a range query (l, r), we know that 2^(factPowSum[r] - factPowSum[l-1]) is the part of final product.
Hope that clarifies.
1 Like
1 2 3 4 1 6 1 8 9 2 1 (Only powers of 2 and 3 are considered from given array).
plzz explain this how this comes from the array 1 2 3 4 5 6 7 8 9 10 after considering the powers of 2 and 3
ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P.
and in this statement what product signifies the final ans of all the factors…!!?
The idea behind splitting input array 1 2 3 4 5 6 7 8 9 10 into two different arrays 1 2 3 4 1 6 1 8 9 2 1 and 1 1 1 1 5 1 7 1 1 5 11, is that we can write product queries (l,r) of input array as product of (l,r) queries in both reduced arrays.
So, For second array, all the elements are co-prime to P, thus, MMI using gcd extended can be used to answer (l,r) queries of this array.
1 Like
For array 1 2 3 4 1 6 1 8 9 2 1, factPowSum array will be
factor = 2, index = 0 => 0 0 1 1 3 3 4 4 7 7 8 8
factor = 3, index = 1 => 0 0 0 1 1 1 2 2 2 4 4 4
(l,r) query for this array = for all factors , prod = (prod*factor^(factPowSum[r] - factPowSum[l-1]))%P.
1 Like
ya that i understanded clearly but how to split the original array in to these diff arrays in terms of powers of factors of p. ?
I create factpowsum array along with taking input, and directly store reduced array im A. Please refer my solution…
1 Like
i am not getting ur solution as i am not a java programmer please u tell me the logic how to convert the array
1 2 3 4 5 6 7 8 9 10
in to the arrays in terms of powers of factors of p which are
1 2 3 4 1 6 1 8 9 2 1 (for power of 2)
1 1 1 1 5 1 7 1 1 5 11(for powers of 3) this is the last thing i am not abl to understand how to do plzz help !
@taran_1407 : plzz help
This is simple, just refer to factPowSum array and give it a try. Read further only after a try.
let ans = 1.
for every factor of P, ans = ans*pow(factor, factPowSum{R+1}-factPowSum{L}).
Now, combining above two sub-problems, we get answer of query as
let ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P.
i write code for the above implementation as
shown below
ans=1;//fact pow sum for the first array
for (std::set<ll>::iterator it=factors.begin(); it != factors.end(); ++it)
{
for (i = 0;i<allfactPowSum.size(); ++i)
{
if(Li>0)
{ans=(ans*(modexp(*it, allfactPowSum[i][Ri]-allfactPowSum[i][Li-1])))%p;}
else ans = (ans*(modexp(*it, allfactPowSum[i][Ri])))%p;
}
}
at the last
ans = (prefixModProd(R+1)*MMI(L) * product(pow(factor, factPowSum[R+1]-factPowSum[L])) )%P.
should be applied in an loop along with calculation of every factor or just outside the loop once ?
you should first calculate (product(pow(factor, factPowSum[R+1]-factPowSum[L]))%P) and then multiply it with (prefixModProd(R+1)*MMI(L))
for(int i = 1; i<= N; i++){
long long x;
cin>>x;//Number read
for(int j = 0; j< fcount; j++){
fsum[j][i] = fsum[j][i-1];//cumulative sum value taken till (i-1)th number.
while(x%factor[j] == 0){//till x is divisible by factors
x/=factor[j]; //divided by factor.
fsum[j][i]++; //Increased fsum value for jth factor at ith number.
}
pcount = max(pcount, fsum[j][i]); //used later, pcount tells maximum power of any factor to be pre-computed.
}