题目概述

求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。

示例程序

如果把系数去掉就是裸的非互质CRT，根据同余方程的同除性，我们可以同除 $r=(atk_i,m_i)$ ，这样的话方程就变成了 ${atk_i\over r}x\equiv {a_i\over r}\ (mod\ {m_i\over r})$ ，当然如果 $a_i$ 不是 $r$ 的倍数方程无解。

把 ${atk_i\over r}$ 除过去，然后做非互质CRT就行了。

解题报告

爆LL丧心病狂，要用快速乘（不过如果不卡LL的话这道题好像的确太送分了）。

#include<cstdio>
#include<cctype>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=100000;

int te,n,m,B[maxn+5];LL A[maxn+5],M[maxn+5],MAX;
multiset<LL> S;multiset<LL>::iterator atk;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline int readL(LL &x){
    LL tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
LL Mul(LL a,LL b,LL MOD){
    if (a<0) a+=MOD;if (b<0) b+=MOD;
    if (b==0) return 0;if (b==1) return a;
    LL c=Mul(a,b>>1,MOD);if ((c+=c)>=MOD) c-=MOD;
    if (b&1) if ((c+=a)>=MOD) c-=MOD;return c;
}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
LL exgcd(LL a,LL b,LL &x,LL &y) {if (!b) return x=1,y=0,a;LL r=exgcd(b,a%b,y,x);return y-=a/b*x,r;}
inline LL Solve(LL A,LL B,LL C){
    if (B<0) B+=C;LL x,y,r=exgcd(A,C,x,y);if (B%r) return -1;
    C/=r;x%=C;if (x<0) x+=C;x=Mul(B/r%C,x,C);return x;
}
#define lcm(A,B) ((A)/gcd((A),(B))*(B))
inline LL China(int n,LL *a,LL *m){
    LL A=a[1],M=m[1];
    for (int i=2;i<=n;i++){
        LL now=Solve(m[i],A-a[i],M);if (now<0) return -1;
        M=lcm(M,m[i]);A=Mul(now,m[i],M)+a[i];if (A>=M) A-=M;
    }
    if (A<MAX) A+=(MAX-A+M-1)/M*M;return A;
}
int main(){
    freopen("dragon.in","r",stdin);freopen("dragon.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);readi(m);S.clear();MAX=0;
        for (int i=1;i<=n;i++) readL(A[i]);
        for (int i=1;i<=n;i++) readL(M[i]);
        for (int i=1;i<=n;i++) readi(B[i]);
        for (int i=1,x;i<=m;i++) readi(x),S.insert(x);
        for (int i=1;i<=n;S.erase(atk),S.insert(B[i++])){
            atk=S.upper_bound(A[i]);if (atk!=S.begin()) atk--;
            MAX=max(MAX,(A[i]+(*atk)-1)/(*atk));
            LL r=gcd(*atk,M[i]);if (A[i]%r) goto OrzZH;
            M[i]/=r;A[i]=Mul(A[i]/r%M[i],Solve((*atk)/r,1,M[i]),M[i]);
        }
        printf("%lld\n",China(n,A,M));continue;OrzZH:puts("-1");
    }
    return 0;
}