Chinese Remainder Theorem

 * Author : Bidhan Roy
 * Required Headers : <vector>
 * If you find any bug report at :
 * Solves equations of the format x % mods[i] = r[i], ( 0<=i<n, where n is the number of equations )

long long CRT(const vector< long long > &r,const vector< long long > &mods){
    long long M=1;
    for(int i=0; i<int(mods.size()); i++) M*=mods[i];
    vector< long long > m, s;
    for(int i=0; i<int(mods.size()); i++){
        long long temp=m[i]%mods[i];
        long long k=0;
        /* if there is a possibility of k being very big, then prime factorize m[i],
         * find modular inverse of 'temp' of each of the factors
         * 'k' equals to the multiplication ( modular mods[i] ) of modular inverses
            if((k*temp)%mods[i]==1) break;
    long long ret=0;
    for(int i=0; i<int(s.size()); i++) {
        ret+=( (m[i]*s[i])%M *r[i] )%M;
        if(ret>=M) ret-=M;
    return ret;

Go Back


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s