Can you please elaborate your doubt? What part you did not understand?
You should ask your question as an actual question in the Forum. You most probably wonāt get an answer if you post your question as an answer to another question
to calculate ( a / b ) % m you need to find multiplicative inverse of 2 modulo m and to calculate that m and b must me coprime.
As said above (AB)%M=((A%M)(B%M)%M)ā¦so lets consider a case where we need to calculate the factorial of 5.What we will do is calculate the factorial and perform the modulo operation on it.
fact=1; for i=1 to i<=5: fact=((fact%M)*(i%M))M; do it this way and you will get the correct answer.
Note : M here being the number whose modulo the answer should be.
Maybe you just shouldnāt use Python for 10^7 operations. Slow languages are slow.
2 Likes
Then maybe they shouldnāt allow it, or (preferably) they should accommodate for itā¦I am learning, and only 1 language at a timeā¦
Also, I think that even with the alternative formula, the timing problem is the same, as (x+1)! is still same number of multiplicationsā¦
So problem is impossible for python? Is that the answer?
You dont need to calculate 107ā¦instead you need to calculate (107)%M for the given M and its not a big deal to calculate (10**7)%Mā¦
Just a guess,
if(x%2==0)
return (x%m*(x/2)%m*(x+1)%m)%m;
else
return (x%m*x%m*((x+1)/2)%m)%m;
It looks like these expression gets overflowed. I am not sure about though. I can give you the testfile on which you are getting wrong answer though.
1 Like
Thanks for the prompt reply but, that doesnt seem to be the problemā¦ Iāve changed the return type to ULL and added yet another mod just to be sure and I only get WA on those 3 fliesā¦ 
weird
I have the same problemā¦ did you find the error?
Modulo and multiplication have the same precedence, so that expression is evaluated left-to-right:
- x=a
- a%m=b
- b*(x/2)=c
- c%m=d
etc. Since b can be around 10^9 and x/2 around 10^18, itās not hard to see that overflow occurs when computing c.
1 Like
Hey @xellos0, nice, thanks for the tip, soā¦ how can I fix that above code?
"This means, we can reduce the task to multiply 3 numbers up to 10^7 (the modulo value) by doing modulo M for each of the numbers before multiplication. "
isnt this what Iām doing?
M <= 10^7ā¦ and if x < M then, yes, you do, as stated in the editorial. Letās store the sum of 1ā1!+2ā2!+ā¦xāx! for each xā¤M
No. We precalculate all the values upto M beforehand. So we can answer for each integer in O(1). Thatās why O(M+N)
1 Like
Is this correct?
unsigned long long int divparcel(unsigned long long int x, int m)
{
if(x%2==0)
return (((x%m*(x/2)%m)%m)(x+1)%m)%m;
else
return ((x%mx%m)%m*((x+1)/2)%m)%m;
}
Just use parentheses, Luke. (And use them correctly. You added them everywhere except where you needed them.)
x/2 is not up to 1e7. x/2 is up to 5e18. (x/2)%M is up to 1e7. Itās b*(x/2)=c, not b*((x/2)%M)=c (note the parentheses).
((((x%m)((x/2)%m))%m)((x+1)%m))%m is the right way. Or just store x,x/2,x+1 in separate variables first, mod these variables and then multiply them while modding again, if you want a cleaner code.
@kuruma,@xellos0 :We can also use modular multiplication for finding (a*b)%m in O(log(n))(it can be optimised further to calculate in constant time).
You can check my solution for further details :-
@knb_dtu Occamās razor: donāt use more than necessary. Anything more than ((a%m)*(b%m))%m is unnecessary. (How much time would you waste during a contest by overcomplicating things like this?)