# HELP in Chinese Remaider Theorem

Can someone help me with the problem FACTMUL on SPOJ (FACTMUL) .
The link to my code is https://ideone.com/hmG0dO
Can someone tell me what is it that I am doing wrong.
Also, I’d be grateful if someone could provide a good source for studying CRT.

There is a mistake where you’re applying CRT, the modulus must be the lowest common multiple of the prime powers involved. I’ve edited it, tell me if it’s fixed.

``````#include<bits/stdc++.h>
#define ll long long int
#define maxN 10000001
#define mod1 186583                     //186583*587117 = 109546051211 (this is mod3)
#define mod2 587117
#define mod3 109546051211

using namespace std;
ll fact1[maxN];
ll fact2[maxN];

ll power(ll base, ll expo, ll mod) {  //fast exponentiation
ll ans = 1;
while(expo) {
if(expo & 1)
ans=(ans * base) % mod;
expo /= 2;
base = (base * base) % mod;
}
return ans;
}

ll inv(ll x, ll m) { //calculating inverse using fermat's little theorem
return(power(x, m - 2, m));
}

int main() {
fact1[0] = fact1[1] = fact2[0] = fact2[1] = 1;

for(ll i = 2; i < 587117; i++) { //precomputing factorials till 587117 as after that the factorials will be divisible by 109546051211
fact1[i] = (i * fact1[i - 1]) % mod1;
fact2[i] = (i * fact2[i - 1]) % mod2;
}

ll n;
cin >> n;

if(n >= 587117) { //if n>=587117 then ans will always be 0
cout << 0 << endl;
return 0;
}

ll r1 = 1, r2 = 1;

for(ll i = 2; <= n; i++) {
r1 = (r1 * fact1[i]) % mod1;          //calculating remainder under 186583
r2 = (r2 * fact2[i]) % mod2;          //calculating remainder under 587117
}

ll res = 0;

res += (((mod2 * inv(mod2, mod1)) % mod3) * r1) % mod3;
res += (((mod1 * inv(mod1, mod2)) % mod3) * r2) % mod3;

cout << ((res + mod3) % mod3) << endl; //added mod3 to take care of negative values
return 0; //I also added this :)
}
``````

P.S. In my opinion, CLRS did a good justice to the topic. Check the chapter on Number Theoretic Algorithms, you’ll surely love it

1 Like

Yes, it worked!! Thanks a lot for identifying my fault.
Moreover, I really appreciate your suggestion