题目描述

本来以为像dp一样注释就够了，看来还是要手推一遍。
基本就是y总的思路。

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//把n个方程逐渐每次消去两个，化为一个，从而得到唯一的同余方程，进而得解。

typedef long long LL;

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,x,y);
    LL z=x;x=y;y=z-(a/b)*y;
    return d;
}

int main()
{
    int n;
    cin>>n;

    //bool has_ans=true;

    LL x=0,a1,m1;   
    cin>>a1>>m1;

    while(n--)
    {
        LL a2,m2;
        cin>>a2>>m2;

        LL k1,k2;
        LL d=exgcd(a1,-a2,k1,k2);

        if((m2-m1)%d)       //如果无解
        {
            //has_ans=false;
            x=-1;
            break;
        }

        k1*=(m2-m1)/d;      //如果有解
        k1=(k1%(a2/d)+a2/d)%(a2/d);

        x=k1*a1+m1;

        LL a=abs(a1/d*a2);
        m1=k1*a1+m1;
        a1=a;
    }

    if(x!=-1) x=(x%a1+a1)%a1;

    cout<<x<<endl;

    return 0;
}