中国剩余定理(非互质求法)

越更越慢,虽然很大一部分是因为智商的问题..
我真的太菜了,,没办法ε=(´ο｀*)))唉..
这个题目https://www.acwing.com/problem/content/description/1300/ emm理解了就不难,但是还是有点思维吧?
怎么写呢?这个题意和上个基本一样,唯一不一样的就是模数不保证两两互质.
首先求n个满足可以简化成两两满足,这是必要的.我们来举个栗子:(因为星号无法正常表示所以我们用两个字体的空格表示相乘)
a1 k1+m1=x(1).a2 k2+m2=x.a&m是已知的,要我们找到且都为正数,要我们找到最小的x使之成立.就是相当于找到最小的k1,k2使之成立.我们把式子进行合并a1 k1+m1=a2 k2+m2.然后就是a1 k1+(-a2) k2=m2-m1,由定理得:if((m2-m1)%gcd(a1,-a2)!=0) 则无解.反之有解.那么原式可以进一步化简,我们令d=(gcd(a1,-a2)),y=(m2-m1)/gcd(a1,-a2).我们可以拿ex_gcd求出a1 k1'+(-a2) k2'=d.其中k1=k1' y.k2=k2' y.
然后因为k1=k1+a2/d k(2).k2=k2+a1/d k(3),把(2)->(1)然后原式进一步成了(a1 (k1+a2/d k))+m1=x,此时的k1是已知的,就是我们拿扩欧求出来的一个解,k是未知的,式子就变成这样了[a1,a2] k+a1 k1+m1=x.反复合并成一个式子,答案就是m1了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=30;
ll a[N],m[N];
ll x,y;
void exgcd(ll aa,ll bb)
{
    if(bb==0)
    {
        x=1,y=0;
        return;
    }
    exgcd(bb,aa%bb);
    ll cx=x,cy=y;
    x=cy;y=cx-aa/bb*cy;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>m[i];
    ll a1=a[1],a2=a[2],m1=m[1],m2=m[2],d=__gcd(a1,-a2),z=(m2-m1)/d,k1,k2;
    if((m2-m1)%gcd(a1,-a2)!=0) {puts("-1");return 0;}
    exgcd(a1,-a2);
    k1=x*z,k2=y*z;
    k1=(k1%abs(a2/d)+abs(a2/d))%abs(a2/d);
    m1=a1*k1+m1;
    a1=abs(a1*a2/d);
    for(int i=3;i<=n;i++)
    {
        a2=a[i],m2=m[i],d=__gcd(a1,-a2),z=(m2-m1)/d;
        if((m2-m1)%gcd(a1,-a2)!=0) {puts("-1");return 0;}
        exgcd(a1,-a2);
        k1=x*z,k2=y*z;
        k1=(k1%abs(a2/d)+abs(a2/d))%abs(a2/d);
        m1=a1*k1+m1;
        a1=abs(a1*a2/d);
    }
    cout<<m1<<endl;
    return 0;
}