长乐 Day 13

求大神请教
一直90

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L=1e5+10;
ll n;
ll a[L],b[L]; 
ll quickpow(ll A,ll B,ll mod)//快速幂 ;
{
    ll ans=0;
    while(B>0)
    {
        if(B&1)
            ans=(ans+A%mod)%mod;
        A=A*2%mod;
        B>>=1;
    }
    return ans;
}
ll exgcd(ll A,ll B,ll &x,ll &y)//扩欧 ;
{
    ll ans=0;
    ll t;
    if(!B)
    {
        x=1;
        y=0;
        return A;
    }
    ans=exgcd(B,A%B,x,y);
    t=x;
    x=y;
    y=t-A/B*y;
    return ans;
}
ll excrt()//扩展中国"AC"定理 ;
{
    ll ans=0;
    ll x,y;
    ll bf=b[1];
    ans=a[1];
    for(int i=2;i<=n;i++)
    {
        ll A=bf;
        ll B=b[i];
        ll C=(a[i]-ans%B+B)%B;
        ll D=exgcd(A,B,x,y);
        //e……变量有点多，快晕了 ;
        if(C%D)
            return -1;
        x=quickpow(x,C/D,B);
        ans+=x*bf;
        bf=bf*B/__gcd(bf,B);
        ans=(ans%bf+bf)%bf;
    }
    if(ans<0)
        ans+=bf;
    return ans;
}
signed main(void)
{
    ll ans=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++)
        a[i]=(a[i]+b[i])%b[i];
    ans=excrt();
    printf("%lld",ans);
    return 0;
}
//stO