题目

每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。

也就是 这个剑的选择已经给定了。

找到选的剑可以通过手写平衡树,但是这是D2T1 手写平衡树太毒瘤了 我们有内置红黑树的set/multiset!支持upper_bound和lower_bound。

显然攻击力可能会重复,所以不能用set。

那就直接multiset上!

选好了显然要计算还需要多少刀才能砍死巨龙。

首先显然要把巨龙砍到再砍一刀生命就为负数,这些刀必须砍。

然后剩下的,设攻击力为s,恢复能力为p,生命为a。

在$\gcd(s,p)|a$的前提下(否则就打不死了),可以把$a,p,s$全部除以$\gcd(a,p)$,这样就方便计算了。下面的$a,p,s$都是除后的。

首先可以exgcd解出最少要砍几刀。

这个值需要$\bmod p$,如果=0并且$a\not =0$,那还最少砍的次数就应该是p。如果a=0,还最少要砍的次数就应该是0。

假设最少要砍k刀。

之后显然多砍p刀是没有影响的。

就得到了一个方程:

$$x\equiv k\pmod p$$且$x\ge k$。

由于这些方程不互质,就不能直接CRT而是要用exCRT。

他们的写法都好玄学我完全看不懂

把每个方程的p分解质因数,拆成$O(\log p)$个方程。

然后把模数的底数相同的合并,就合并成$O(\log \mathrm{lcm})$个方程了。

但是分解是$O(n\sqrt{p})$的好慢啊...

可以先计算出lcm并对lcm分解质因数 显然不需要Pollard Rho可以直接根号分解,然后底数就只有可能是这$O(\log \textrm{lcm})$个质因数。

分解的时候就只需要考虑这些质因数了 。

exCRT出答案以后,如果不满足$\ge k$的限制,,, 由于答案是$\bmod \textrm{lcm}$意义下的,设算出来答案为S,$\max\{k\}=M$,答案只需要+$\lceil\frac{M-S}{\textrm{lcm}}\rceil \textrm{lcm}$就好。

显然$\lceil\frac{M-S}{\textrm{lcm}}\rceil=\lfloor\frac{M-S}{\textrm{lcm}}\rfloor+[(M-S)\bmod \text{lcm} \not=0]$。

时间复杂度$O(n\log \textrm{lcm} +\sqrt{\textrm{lcm}})$。

/*
Author: CNYALI_LK
LANG: C++
PROG: dragon.cpp
Mail: cnyalilk@vip.qq.com
*/ 
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
multiset<ll> t;
multiset<ll>::iterator it;
ll a[102424],p[102424],b[102424],ys[102424],atl[102424],_ans;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}
ll Calc(ll a,ll b,ll &c,ll &d,ll &e){
    e=b/a;
    b%=a;
    ll h=gcd(a,c),x,y;
    if(b%h)return 1;
    a/=h;b/=h;c/=h;
    exgcd(a,c,x,y);
    if(b)
        x=((x%c+c)%c*b+c-1)%c+1;
    else
        x=0;
    e+=x;
    d=e%c;
    chkmax(_ans,e);
    return 0;
}
ll st,ax[102424],px[102424];
ll mul(ll a,ll b,ll p){
    ll c=0;
    for(;b;b>>=1,a=(a+a)%p)if(b&1)c=(c+a)%p;
    return c;
    
}
ll CRT(ll n){
    ll s=1,sum=0,x,y;
    for(ll i=1;i<=n;++i)s*=px[i];
    for(ll i=1;i<=n;++i){
       exgcd(s/px[i],px[i],x,y);
       x=(x%px[i]+px[i])%px[i];
       sum=(sum+mul(mul(x,(s/px[i]),s),ax[i],s))%s;
    }
    return sum;
}
void calc(ll n){
    ll s=1,h,pxy,xl,stdc;
    for(ll i=1;i<=n;++i)s=s/gcd(s,p[i])*p[i];
    stdc=s;
    st=0;
    for(ll i=2;i*i<=s;++i)if(!(s%i)){
        ++st;
        px[st]=1;
        ax[st]=0;
        while(!(s%i)){
            s/=i;
            px[st]*=i;
        }
        xl=1;
        for(ll j=1;j<=n;++j)if(!(p[j]%i)){
            pxy=1;
            while(!(p[j]%i)){
                pxy*=i;
                p[j]/=i;
            }
            if(pxy>xl){
                if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
                else {xl=pxy;ax[st]=ys[j]%pxy;}
            }
            else{
                if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
            }
        }
    }
    if(s>1){
        ++st;
        px[st]=s;
        ax[st]=0;
        xl=1;
        for(ll j=1;j<=n;++j)if(!(p[j]%s)){
            pxy=1;
            while(!(p[j]%s)){
                pxy*=s;
                p[j]/=s;
            }
            if(pxy>xl){
                if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
                else {xl=pxy;ax[st]=ys[j]%pxy;}
            }
            else{
                if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
            }
        }
    }
    ll ans=CRT(st),ax;
    if(ans<_ans){
        ax=((_ans-ans)/stdc)+!!((_ans-ans)%stdc);
        ans=ans+ax*stdc;
    }
    printf("%lld\n",ans);
}
int main(){
    freopen("dragon.in","r",stdin);
    freopen("dragon.out","w",stdout);
    ll T,n,m,s;
    T=read();
    for(;T;--T){
        n=read();m=read();
        for(ll i=1;i<=n;++i)a[i]=read();   
        for(ll i=1;i<=n;++i)p[i]=read();
        for(ll i=1;i<=n;++i)b[i]=read();
        t.erase(t.begin(),t.end());
        for(ll i=1;i<=m;++i)t.insert(read());
        ll ok=1;
        _ans=0;
        for(ll i=1;i<=n;++i){
            it=t.upper_bound(a[i]);
            if(it==t.begin())s=*it;
            else s=*(--it);
            t.erase(it);
            if(Calc(s,a[i],p[i],ys[i],atl[i])){printf("-1\n");ok=0;break;};
            t.insert(b[i]);
        }
        if(ok)calc(n);
    }
    return 0;
}

标签: 数论

添加新评论