I had used the logarithmic approach as discussed in the editorial but I am getting the wrong answer for x=y (where x and y are very big) but it is working fine on my local system. I am not able to figure out the exact reason why it is behaving differently on CF judge and my local system. Can someone please help me out to understand it?

Thanks in advance.

my solution

yes, I also had done the same. I had used heap(priority_queue) instead of sorting.

But finally got accepted with (N+M)*K.

Did anyone else also find time-limit too strict for problem div2 D? got TLE with N*K*logK solution.

It will work because of inverse modulo property. Suppose you want to find R = P / Q and it can be calculated using modular arithmetic as well ( given that Q is coprime to mod, it will become ( R = P * invQ ) % mod , where invQ is modular inverse of Q such that ( Q * invQ = 1 ) % mod ).

let g = gcd(P,Q). then P = g * p and Q = g * q, invQ = invg * invq,

So, ( P * invQ = p * g * invg * invq = p * invq * ( g * invg ) = p * invq ) % mod, because ( g * invg = 1 ) % mod , due to inverse property.

you can see simplified as well as non-simplified fraction leads to the same result.

I hope it helps.

Happy Coding :)