zcmimi's blog
查看原题

点击跳转

先预处理出每次的攻击力c_i,推荐使用multiset

问题变成了:

c_ix \equiv a_i \pmod{p_i}

可是题目并没有保证a_i\le p_i

仔细阅读题目,可以发现当a_i>p_i的时候一定满足p_i=1

那么在这个情况答案就是\max_{i=1}^n(\left \lceil \frac{a_i}{c_i} \right \rceil)

接下来就是a_i \le p_i的情况了

标准的Excrt要求x的系数必须为1

我们可以转化为Exgcd解不定方程

c_ix \equiv a_i \pmod{p_i}

c_ix + p_iy = a_i

可以用Exgcd解出一组解sx,sy,并得出

x=sx+\lambda \frac{p_i}{\gcd(c_i,p_i)}

也就是

x\equiv sx \pmod{\frac{p_i}{\gcd(c_i,p_i)}}

这样就可以用Excrt求解了

特判:

  1. 所有a_i=p_i,那么所有sx=0,按照上面的方法解是不对的(答案会等于0)

    直接求出杀死每条龙所需的刀数然后所有刀数求一个lcm即可

    也就是lcm_{i=1}^n(\frac{p_i}{\gcd(c_i,p_i)})

  2. c_ip_i的倍数的时候杀不死这条龙

    但这时如果a_i=p_i,这个方程相当于没用,可以换成x \equiv 0 \pmod 1之类的

记得全部开long long,用龟速乘

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
#define ll long long
#define MB template <class T>il
#define Fur(i,x,y) for(int i(x);i<=y;++i)
MB T MAX(T x,T y){return x>y?x:y;}
MB T GCD(T x,T y){return y?GCD(y,x%y):x;}
using namespace std;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(string &ch){ch.clear();if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}ch+=c;while((c=gc())!=EOF&&!isspace(c))ch+=c;if(c==EOF)__=1;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}il void out(string s){for(int i=0;s[i];i++)pt(s[i]);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=100011;
il ll mul(ll x,ll y,ll p){
    ll res=0;
    while(y){
        if(y&1)res=(res+x)%p;
        y>>=1;x=(x+x)%p;
    }
    return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y),t=x;
    x=y;y=t-a/b*y;
    return gcd;
}
int n,m;ll a[N],p[N],c[N],ext[N];
il ll excrt(){
    ll ans=a[1],M=p[1],t,y;
    Fur(i,2,n){
        ll b=p[i],c=(a[i]-ans%b+b)%b,gcd=exgcd(M,b,t,y); //Mx \equiv c \pmod b
        if(c%gcd)return -1;
        t=mul(t,c/gcd,b/gcd);
        ans+=t*M;
        M*=b/gcd;
        ans=(ans%M+M)%M;
    }
    return ans;
}
il void solve2(){
    ll ans=1;
    Fur(i,1,n)ll x=p[i]/GCD(p[i],c[i]),ans=ans/GCD(ans,x)*x;
    out(ans,ln);
}
il void solve3(){
    ll ans=0;
    Fur(i,1,n)ans=MAX(ans,(a[i]+c[i]-1)/c[i]);
    out(ans,ln);
}
il void solve(){
    in(n,m);
    Fur(i,1,n)in(a[i]);
    Fur(i,1,n)in(p[i]);
    Fur(i,1,n)in(ext[i]);
    multiset<ll>s;ll x;
    Fur(i,1,m)in(x),s.insert(x);
    Fur(i,1,n){
        multiset<ll>::iterator it;
        if(a[i]<=*s.begin())it=s.begin();
        else it=--s.upper_bound(a[i]);
        c[i]=*it;
        s.erase(it);s.insert(ext[i]);
    }
    Fur(i,1,n)if(p[i]!=a[i])goto skip;
    solve2();return;// 所有ai=pi
    skip:;
    Fur(i,1,n)if(p[i]!=1)goto SKIP;
    solve3();return;// 所有pi=1
    SKIP:;
    Fur(i,1,n)c[i]%=p[i];
    Fur(i,1,n)if(p[i]==c[i]){
        if(a[i]==p[i])c[i]=1,p[i]=1,a[i]=0;
        else return void(out("-1\n"));
    }
    Fur(i,1,n){
        ll sx,sy,gcd=exgcd(c[i],p[i],sx,sy);
        if(a[i]%gcd)return void(out("-1\n"));
        p[i]/=gcd;
        sx=(sx%p[i]+p[i])%p[i];
        a[i]=mul(sx,a[i]/gcd,p[i]);
    }
    out(excrt(),ln);
}
int main(){
    int T;in(T);
    while(T--)solve();
    flush();
}
LG 4774 [NOI2018]屠龙勇士
comment评论
Search
search