EXCRT 学习记录

__vector__ · 2022-05-27 22:28:05 · 个人记录

前言：

看了 \color{black}\text{W}\color{red}\text{YXkk} 和 \color{black}\text{阮}\color{red}\text{行止} 的题解我总算是会了

正文：

先考虑只有两个方程的情况：

可以转化为：

显然可得：

移项之后：

然后解出 k_1 和 k_2（求解这种方程的代码下附，其实这么简单的东西自己推一下也能推出解法）
然后 x 就是 r_1 + k_1m_1（没错，不用 k_2 和 m_2 也行）

然后就是合并这两个方程，这里用到了一个定理：

设这两个方程有一个特解 x_0，满足

那么它们的通解 x 满足

这样就和并成了一个方程，但是这个做法我不会证明

现在就是把方程组的每个方程都压入队列中，每次取队首的两个方程进行合并再压入队列中，直到只剩一个方程。显然这个方程的解就是最终的解。

额外：

放一份求解形如 ax+by=c 这样的方程的代码（已知 a,b,c）

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    ll exgcd(ll a,ll b,ll& x,ll& y)
    {
        if(!b)
        {
            x=1;
            y=0;
            return a;
        }
        ll ans=exgcd(b,a%b,x,y);
        ll tmp=x;
        x=y;
        y=tmp-a/b*y;
        return ans;
    }
    ll a,b,c,x0,y0,x,y;
    void main()
    {
        printf("Solving ax+by=c\n");
        printf("a: ");
        scanf("%lld",&a);
        printf("b: ");
        scanf("%lld",&b);
        printf("c: ");
        scanf("%lld",&c);
        int d=exgcd(a,b,x0,y0);
        if(c%d!=0)
        {
            printf("No\n");
            return;
        }
        int k=c/d;
        x=x0*k;
        y=y0*k;
        printf("%lld * %lld + %lld * %lld = %lld",a,x,b,y,c);
    }
}
int main()
{
    Main::main();
    return 0;
}

注意：

exgcd 的结果可能是负数

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=1e5+5;
    typedef long long ll;
    typedef __int128 ll128;
    typedef pair<ll128,ll128> pr;
    ll gcd(ll a,ll b)
    {
        return !b?a:gcd(b,a%b);;
    }
    ll lcm(ll a,ll b)
    {
        return a/gcd(a,b)*b;
    }
    ll exgcd(ll a,ll b,ll& x,ll& y)
    {
        if(!b)
        {
            x=1;
            y=0;
            return a;
        }
        ll ans=exgcd(b,a%b,x,y);
        ll tmp=x;
        x=y;
        y=(ll128)tmp-ll128(a/b)*(ll128)y;
        return ans;
    }
    pr axbyc(ll a,ll b,ll c)
    {
        ll x0,y0;
        ll d=exgcd(a,b,x0,y0);
        ll128 k=c/d;
        ll128 x=(ll128)x0*k;
        ll128 y=(ll128)y0*k;
        return make_pair(x,y);
    }
    int n;
    ll128 m[maxn],r[maxn];
    queue<pr> equ;
    ll128 gsc(ll128 a,ll128 b,ll128 mod)
    {
        ll128 ret=0;
        while(b)
        {
            if(b&1)ret=(ret+a)%mod;
            ret=ret*2%mod;
            b>>=1;
        }
        return ret;
    }
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            ll mi,ri;
            scanf("%lld%lld",&mi,&ri);
            equ.push(make_pair(mi,ri));
        }
        while(equ.size()>1)
        {
            pr _=equ.front();
            equ.pop();
            pr __=equ.front();
            equ.pop();
            ll128 m1=_.first;
            ll128 r1=_.second;
            ll128 m2=__.first;
            ll128 r2=__.second;
            pr ___ = axbyc(m1,-m2,r2-r1);
            ll128 k1=___.first;
            ll128 x=r1+(ll128)k1*(ll128)m1;
            equ.push(make_pair(lcm(m1,m2),(x%(ll128)lcm(m1,m2)+(ll128)lcm(m1,m2))%(ll128)lcm(m1,m2)));
        }
        printf("%lld",(ll)equ.front().second);
    }
}
int main()
{
    Main::main();
    return 0;
}