When you count invM*rj*M mod M*pj you can get number > int64. But you can use this: a*b mod a*c=a*(b mod c). In our situation M*(invM*rj mod p[j]).

Here is the solutuion
http://xoptutorials.com/index.php/2017/01/01/timus1926/

WA5 is about this case (overflow test, WA9 and WA15 too), but formula I used still gets int64 overflow (chinese remainders), so I had to devise "short long arithmetics" (4 qwords to store result with base-2^32 digits, then fetching remainder via base-2^4 interpretation - that fits unsigned int64). Timing is still bad - like 0.14 sec, and was like 0.5 sec without bitwise optimizations. Your hint though allowed to fetch remainder via base-2^8 interpretation which shortened timing down to 0.062s sec.

Edited by author 12.08.2022 05:27

Finally AC 0.031 without long arithmetics. Another hint - do not process primes one after another because in the end you will get a*b%c where both 'a' and 'b' are close to 2^63. Instead process first 9 primes individually and last 6 primes individually (product of both sequences is on the verge of 2^32). Then you may combine result within 2^64 using "dirty hack" mentioned by Felix_Mate :)

P.S: I finally understood why you had 'inv' there, but in this case no mod operations are necessary at all (except during calculating inverse which is mod 47 at most), and this way of getting the answer (POW instead of GCD) works fine with sequential primes processing, no need to split them in two parts and pray for no overlow.