题目描述

表达整数的奇怪方式

（1）用多组x=kiai+mi来表示整数x

（2）就转变成k1a1-k2a2=m2-m1，其形式与扩展欧几里得算法相似，所以可以利用扩展欧几里得算法来求出系数k1,k2

（3）因为通过变形得：x=k1a1+m1+k(a1a2/d),其中k为未知数，而通过等效替代上式又可以变成：x=ka+m，与刚开始相似，所以通过不断地与后式构成方程组

（4）因为m=ka+x(其中k的符号通过在运算中给除法加绝对值来控制其始终是正数)，通过取余来求得x

C++ 代码

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

typedef long long LL;

//扩展欧几里得算法求最大公约数
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main()
{
    int n;
    cin>>n;
    bool has_answer = true;
    LL a1,m1;
    cin>>a1>>m1;
    for(int i=0;i<n-1;i++)
    {
        LL a2,m2;
        cin>>a2>>m2;
        LL k1,k2;
        LL d=exgcd(a1,a2,k1,k2);    //k1a1-k2a2=m2-m1=d，两者公约数相同
        if((m2-m1)%d)
        {
            has_answer=false;
            break;
        }
        k1*=(m2-m1)/d;       //因为m2-m1是k2a2-k1a1的若干倍，所以要k1也扩大若干倍
        LL t=a2/d;            //定义一个变量t存储a2/d的值
        //k1=k1+k*(a2/d),求k1即是求余数
        k1=(k1%t+t)%t;      //变成最小的正整数解（k的通解）k1+k*a2/d(为了包含所有的解所以要/d)

        //覆盖原来的a1,m1，形成新的a1,m1，与接下来的a2,m2再进行混合运算
        m1=a1*k1+m1;
        a1=abs(a1/d*a2);      
    }
    if(has_answer)
    {
        cout<<(m1%a1+a1)%a1<<endl; //避免答案出现负数（m1=x+ka1）
    }
    else puts("-1");
    return 0;
}