src/math/crt.hpp

• View this file on GitHub
• Last update: 2026-01-30 22:16:29+09:00
• Include: #include "src/math/crt.hpp"

Depends on

• src/template.hpp

Code

#pragma once
#include "../template.hpp"

//acl(template)
template<typename T> constexpr pair<T,T> inv_gcd(T a,T b){
    a=(a%b+b)%b;
    if(a==0) return {b,0};
    T s=b,t=a;
    T m0=0,m1=1;

    while(t){
        T u=s/t;
        s-=t*u;
        m0-=m1*u;
        auto tmp=s;
        s=t;
        t=tmp;
        tmp=m0;
        m0=m1;
        m1=tmp;
    }
    if(m0<0) m0+=b/s;
    return {s,m0};
}

template<typename T> T inv_mod(T x,T m){
    assert(1<=m);
    auto z=inv_gcd(x,m);
    assert(z.first==1);
    return z.second;
}

template<typename T> pair<T,T> crt(const vector<T>& r,const vector<T>& m){
    assert(r.size()==m.size());
    int n=int(r.size());
    T r0=0,m0=1;
    for(int i=0;i<n;i++){
        assert(1<=m[i]);
        T r1=(r[i]%m[i]+m[i])%m[i],m1=m[i];
        if(m0<m1){
            swap(r0,r1);
            swap(m0,m1);
        }
        if(m0%m1==0){
            if(r0%m1!=r1) return {0,0};
            continue;
        }
        T g,im;
        tie(g,im)=inv_gcd(m0,m1);

        T u1=(m1/g);
        if((r1-r0)%g) return {0,0};

        T x=(r1-r0)/g%u1*im%u1;
        r0+=x*m0;
        m0*=u1;
        if(r0<0) r0+=m0;
    }
    return {r0,m0};
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/math/crt.hpp"

//acl(template)
template<typename T> constexpr pair<T,T> inv_gcd(T a,T b){
    a=(a%b+b)%b;
    if(a==0) return {b,0};
    T s=b,t=a;
    T m0=0,m1=1;

    while(t){
        T u=s/t;
        s-=t*u;
        m0-=m1*u;
        auto tmp=s;
        s=t;
        t=tmp;
        tmp=m0;
        m0=m1;
        m1=tmp;
    }
    if(m0<0) m0+=b/s;
    return {s,m0};
}

template<typename T> T inv_mod(T x,T m){
    assert(1<=m);
    auto z=inv_gcd(x,m);
    assert(z.first==1);
    return z.second;
}

template<typename T> pair<T,T> crt(const vector<T>& r,const vector<T>& m){
    assert(r.size()==m.size());
    int n=int(r.size());
    T r0=0,m0=1;
    for(int i=0;i<n;i++){
        assert(1<=m[i]);
        T r1=(r[i]%m[i]+m[i])%m[i],m1=m[i];
        if(m0<m1){
            swap(r0,r1);
            swap(m0,m1);
        }
        if(m0%m1==0){
            if(r0%m1!=r1) return {0,0};
            continue;
        }
        T g,im;
        tie(g,im)=inv_gcd(m0,m1);

        T u1=(m1/g);
        if((r1-r0)%g) return {0,0};

        T x=(r1-r0)/g%u1*im%u1;
        r0+=x*m0;
        m0*=u1;
        if(r0<0) r0+=m0;
    }
    return {r0,m0};
}

Back to top page