[NOI2018]屠龙勇士

题目描述

题解

考虑增量法。

假设我们已经做完了前k个条件，前面的模数连乘起来的结果为M，答案为X，当前的攻击力为x，龙的血量为a。

那么我们这一次的答案的表达形式是X+t*M的。

这一次需要满足的是x(X+t*M)≡a(%p).

只有t一个未知量，用exgcd就可以解了。

然后就是恶心的特判了。。。

代码

#include<iostream>

#include<cstdio>

#include<set>

#include<cmath>

#define N 100002

using namespace std;

typedef long long ll;

ll x,y,p[N],a[N],b[N],M,X,n,m,tag,t;

multiset<ll>s;

multiset<ll>::iterator it;

inline ll rd(){

    ll x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

inline ll power(ll x,ll y,ll mod){

    x=(x%mod+mod)%mod;y=(y%mod+mod)%mod;

    ll ans=;

    while(y){

        if(y&)(ans+=x)%=mod;

        (x<<=)%=mod;

        y>>=;

    }

    return ans;

}

void exgcd(ll a,ll b){

    if(!b){x=;y=;return;}

    exgcd(b,a%b);

    ll k=x;x=y;y=k-a/b*y;

}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline void EXCRT(ll a,ll b,ll c){

    ll aa=x*M,bb=c,cc=b-a*X;

    ll g=gcd(aa,bb);

    if(cc%g){tag=;return;}

    if(c==){

        bb/=g;

        ll p=M;M*=bb;

        X+=max(0ll,(ll)ceil((double)((double)b/a-X)/p))*p;

        return;

    }

    aa/=g;bb/=g;cc/=g;

    exgcd(aa,bb);

    x=power(x,cc,bb);

    ll p=M;M*=bb;

    x=power(x,p,M);

    X=(X+x)%M;

}

int main(){

//    freopen("1.in","r",stdin);

    t=rd();

    while(t--){

    n=rd();m=rd();tag=;s.clear();M=;X=;

    for(int i=;i<=n;++i)a[i]=rd();

    for(int i=;i<=n;++i)p[i]=rd();

    for(int i=;i<=n;++i)b[i]=rd();

    for(int i=;i<=m;++i)x=rd(),s.insert(x);

    for(int i=;i<=n;++i){

        it=s.upper_bound(a[i]);if(it!=s.begin())--it;

        x=*it;s.erase(it);

        EXCRT(x,a[i],p[i]);

        if(tag)break;

        s.insert(b[i]);

    }

    if(tag)printf("-1\n");

    else cout<<X<<endl;

   }

    return ;

}