crt.sublime-snippet

<snippet>
	<content><![CDATA[

int x,y,GCD;
void extendedEuclid(int a,int b){
    // To calculate Ax + By = C where C is a mulitple of divior of A and B (K*gcd(A,B))
    if(b==0){
        x = 1; y = 0;GCD =a; 
        return;
    }
    extendedEuclid(b,a%b);
    int x1 = y;
    int y1 = x - (a/b)*y;

    x = x1;
    y = y1;
    // Multiply by K to get the final answer
}

int modularInverse(int a,int m){
    extendedEuclid(a,m);
    return (x+m)%m;
}

int CRT(vector<int> num, vector<int> rem){
    
    int prod=1ll;
    vector<int> pp;
    pp.clear();
    for(int i=0;i<num.size();i++){
        prod*=num[i];
    }
    for(int i=0;i<num.size();i++){
        pp.push_back(prod/num[i]);
    }
    vector<int> inv;
    inv.clear();
    for(int i=0;i<pp.size();i++){
        inv.pb(modularInverse(pp[i],num[i]));
    }
    int ans=0ll;
    for(int i=0;i<inv.size();i++){
        ans+=(((inv[i]*rem[i])%prod)*(pp[i]%prod))%prod;
        ans%=prod;
    }
    return ans;
}

]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>crt</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>