|
|
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]). 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. 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. I know there are some rules for modulo by 3 or 5. I'm not sure applying only those two rules will help. Or are there are generic rule for modulo by prime numbers? Edited by author 04.02.2014 03:20 Chinese Remainder Theorem does the trick. Какие ограничения накладываются на c[i]? Какой максимальной длины может быть это число? 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47 Edited by author 28.10.2012 11:22 Edited by author 28.10.2012 11:22 Edited by author 28.10.2012 11:22 |
|
|