P1495

Aryper · 2021-11-19 08:52:47 · 个人记录

【模板】中国剩余定理(CRT)/曹冲养猪

逆元见 P1082。

我们有 m_1,m_2,\cdots,m_k 两两互质，定义 m=\prod_{i=1}^k m_i，M_i=\dfrac{m}{m_i}，t_i 为满足 M_it_i\equiv 1\pmod {m_i} 的一个解，则线性同余方程组

有解，解为 x=\sum_{i=1}^ka_iM_it_i。

这本质上其实是一个构造。

然后这里求最小非负整数解，我们通过求余的一系列操作 O(1) 可完成。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=10;

ll n,x,m_,y;

ll m[N+5],a[N+5],M[N+5],t[N+5];

inline ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(b==0) {x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);y-=a/b*x;
    return d;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();

    m_=1;
    for(ll i=1;i<=n;i++) {
        m[i]=read();a[i]=read();
        m_=m_*m[i];
    }

    for(ll i=1;i<=n;i++) {
        M[i]=m_/m[i];y=0;
        exgcd(M[i],m[i],t[i],y);
        x+=a[i]*M[i]*t[i];
    }

    x=(x%m_+m_)%m_;

    writeln(x);

    return 0;
}