前言：

在本章会介绍扩展中国剩余定理，至于为什么不介绍中国剩余定理，因为我懒，而且我认为扩展定理可以解决一切。

扩展中国剩余定理：

 

 

 解决形如以上方程的最小非负数x。

解决步骤简要分析：

设前k-1个方程解出的答案为ans,前k-1个m的lcm=M,则新的ans为(ans+M*x)，且(ans+M*x)≡ak(mod mk)。

这里的x为一个系数，之所以是M*x是因为满足当前的条件同时，还要满足之前的条件。所以就是M*x≡ak-ans(mod mk)，那么转换为M*x+mk*y=ak-ans。那么这个式子就是个扩欧了，直接求出x,新的ans=ans+x*M。下面给出代码：

#include<bits/stdc++.h>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define ll long long
using namespace std;
ll read()
{
    ll out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
}
int k;
ll a[100010],b[100010];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
ll mul(ll A,ll B,ll mod)//快速乘
{
    ll ans=0;
    while(B>0)
      {
        if(B & 1) ans=(ans+A%mod)%mod;
        A=(A+A)%mod;
        B>>=1;
      }
    return ans;
}
int main()
{
    k=read();
    fo(i,1,k)
    {
        scanf("%lld%lld",&b[i],&a[i]);
    }
    fo(i,1,k) a[i]=(a[i]+b[i])%b[i];///预处理
    ll ans=0,lcm=1,A,B,C,gcd,x,y;
    fo(i,1,k)
    {
        A=lcm;
        B=b[i];
        C=(a[i]-ans%b[i]+b[i])%b[i];
        ll gcd=exgcd(A,B,x,y);
        if(C%gcd>0)
        {
            return 0;
        }
        x=mul(x,C/gcd,b[i]);
        ans+=lcm*x;
        lcm=lcm/gcd*b[i];
        ans=(ans%lcm+lcm)%lcm;
    }
    printf("%lld",ans);
    return 0;
}

结合代码应该会更好的理解。

下面给出一道例题：

4774屠龙勇士

中间的转换很简单，最后会变成一系列同余方程，这时上exrct就行了。

注：最后求出的ans不一定就是最后的ans,因为ans还要满足将每个龙杀死，所以在处理的时候要注意这一点。

在这里引出一个模型，有n个苹果，每个篮子可以装m个苹果，那么需要(n-1)/m+1个篮子才能保证装完。

下面代码会有2处体现这个模型，放代码：

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
const int maxn=100005;
int T,n,m,b[maxn],t[maxn];
long long a[maxn],p[maxn],mx;
multiset<long long> s;
multiset<ll>::iterator it;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tx=x;
    x=y;
    y=tx-a/b*y;
    return d;
}
ll excrt()
{
    ll ans=0,lcm=1,x,y,gcd,A,B,C;
    fo(i,1,n)
    {
        A=(__int128)b[i]*lcm%p[i];
        B=p[i];
        C=(a[i]-b[i]*ans%p[i]+p[i])%p[i];
        gcd=exgcd(A,B,x,y);
        x=(x%p[i]+p[i])%p[i];
        if(C%gcd) return -1;
        ans+=(__int128)(C/gcd)*x%(B/gcd)*lcm%(lcm*=B/gcd);
        ans%=lcm;
    }
    if(ans<mx) ans+=((mx-ans-1)/lcm+1)*lcm;//第二处
    return ans;
}
int main()
{
    cin>>T;
    while(T--)
    {
        s.clear(),mx=0;
        cin>>n>>m;
        fo(i,1,n) cin>>a[i];
        fo(i,1,n) cin>>p[i];
        fo(i,1,n) cin>>t[i];
        fo(i,1,m) 
        {
            int x;
            cin>>x;
            s.insert(x);
        }
        fo(i,1,n)
        {
            it = s.upper_bound(a[i]);
            if(it!=s.begin()) it--;
            b[i]=*it;
            s.erase(it);
            s.insert(t[i]);
            mx=max(mx,(a[i]-1)/b[i]+1);//第一处
        }
        cout<<excrt()<<endl;
    }
    return 0;
}

通过这个代码让我学习到了multiset，真是个好东西啊。

multiset<long long> s;
multiset<ll>::iterator it；

it = s.upper_bound(a[i]);
            if(it!=s.begin()) it--;
            b[i]=*it;
            s.erase(it);
            s.insert(t[i]);

这一段的语法可以记一记，讲实话stl真是我的一大痛点啊。

总结：

excrt不难，还挺有趣。（又在水总结）