HELP in Chinese Remaider Theorem

help
1

Can someone help me with the problem FACTMUL on SPOJ (FACTMUL) .
The link to my code is hmG0dO - Online C++0x Compiler & Debugging Tool - Ideone.com
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.

2

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 :slightly_smiling_face:

1 Like
3

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