I was trying to solve the first two subtasks of SEGPROD but it was giving me NZEC everytime. I don’t know what made the program crash. Please help me debug it.
I am using the following logic to answer all the queries:
Let N = Product of all elements (from 1 to N ) (modulo P) Let L = prefix product upto L-1 (modulo P) Let R = suffix product from R+1 (modulo P) Answer = (N * modularInverse(Q) * modularInverse(R)) (modulo P);
I tested this logic for sample inputs and some other Test Cases and it was giving correct output.
For first subtask P was prime and all the numbers were between 1 & P-1. So using MMI I could have got atleast 20 points. I am using Fermats’s little theorem to find MMI.
Here is the link to my solution using recursive version of it.
And here is the link to my solution with iterative version of it.
But they both are giving NZEC for reasons unknown to me.
Now for Subtask 2: P = x^k where x is prime and all the numbers are in range 1 to P-1. So I tried using Extended Euclidean algorithm to find MMI of numbers as it works when number and P are co-prime. This holds for both the subtasks and should atleast pass them. Here is the link to it.
The normal version of the code by by doing multiplication everytime for all the queries giving TLE is here. The code works fine. I just replaced running the loop everytime by the method mentioned above which gives result in constant time for each query. I can’t understand what is wrong with my MMI codes. Please help.