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]).

what is wrong here?

for (int i =0; i< 15;++i)
{
int p = primes[i];
if ( c % p == 0)
{
   unsigned long long M = c / p;
   unsigned long long M_inv = inverse[i][ M % p ] ;
   unsigned long long h = M_inv * m[ i ];
   // r = (r + h * M ) % c

   unsigned long long high_M = (M >> 32 ) & 0xFFFFFFFFULL;
   unsigned long long low_M = ( M & 0xFFFFFFFFULL);

   // h * M= h * (high_M * 2^32 + low_M)
   unsigned long long high_h = high_M * h;
   unsigned long long e = (high_h >> 32) & 0xFFFFFFFFULL;
   unsigned long long f = (high_h & 0xFFFFFFFFULL);

   // high_h = e*2^32 + f

// h*M = h*(high_M*2^32 + low_M) = high_h * 2^32 + low_M * h =
// = (e*2^32 + f)*2^32 + low_M * h = e*2^64 + f*2^32 + low_M * h

    e = (e << 48) % c;
    e = (e << 3 ) % c;
    e = (e << 3 ) % c;
    e = (e << 3 ) % c;
    e = (e << 3 ) % c;
    e = (e << 3 ) % c;
    e = (e << 1 ) % c;

   e = (e + (f << 32) ) % c;
   e = (e + low_M * h ) % c;

   r = (r + e ) % c;
 }
}

Brute-force approach using BigInteger in Java exceeds time limit in test#13. Can anybody give a hint, please?

Thanks.

Какие ограничения накладываются на c[i]? Какой максимальной длины может быть это число?