咕咕来更博了 ( ̄︶ ̄*))

发现每一条龙对应的剑是可以预处理的…… 设第 $i$ 条龙对应的剑的攻击力为 $c_i$ .

接着设 $x$ 为最小挥剑次数,于是可以列出同余方程组:
$$
\begin{cases}
x\times s_1=a_1+p_1\times y\\
x\times s_2=a_2+p_2\times y\\
\cdots\\
x\times s_n=a_n+p_n\times y\\
\end{cases}
\Rightarrow
\begin{cases}
x\times s_1\equiv a_1\pmod{p_1}\\
x\times s_2\equiv a_2\pmod{p_2}\\
\cdots\\
x\times s_n\equiv a_n\pmod{p_n}\\
\end{cases}
$$
貌似可以用中国神鱼剩余定理做,不过朴素的中国神鱼剩余定理是没有左边的 $c_i$ 的。怎么将 $c_i$ 调走呢?
$$
x\times c_i\equiv a_i\pmod{p_i}\
x\times c_i=a_i+y\times p_i\
x\times c_i+y\times p_i=a_i\
$$


如何用扩展欧几里得求方程 $ax+by=c\ (a,b,c>0)$ 的通解?

显然扩展欧几里得一般用于求 $ax+by=(a,b)$ 的一组特殊解。对于上面的式子,当且仅当 $c|(a,b)$ 时才有解,否则无解。

对于 $ax’+by’=(a,b)$ ,将两边同时乘上 $\frac{c}{(a,b)}$ ,也就等于 $ax’\frac{c}{(a,b)}+by’\frac{c}{(a,b)}=c$ 。原方程为 $ax+by=c$ ,对 $ax’+by’=(a,b)$ 使用 $exgcd$ 求出 $x’$ 后,我们便可以得到原方程的一个解了:$x=x’\frac{c}{(a,b)}$ ,那么 $x$ 的通解即为 $x’\frac{c}{(a,b)}+k\frac{b}{(a,b)}$ ,于是我们可以得到同余方程:
$$
x\equiv x’\frac{c}{(a,b)}\pmod{\frac{b}{(a,b)}}
$$


放到题目中,最终需要解决的方程组为:
$$
\begin{cases}
x\equiv x’_1\frac{a_1}{(c_1,p_1)}\pmod{\frac{p_1}{(c_1,p_1)}}\\
x\equiv x’_2\frac{a_2}{(c_2,p_2)}\pmod{\frac{p_2}{(c_2,p_2)}}\\
\cdot\\
x\equiv x’_n\frac{a_n}{(c_n,p_n)}\pmod{\frac{p_n}{(c_n,p_n)}}\\
\end{cases}
$$
我们需要求出一个最小的 $x$ ,由于模数不一定是质数,需要用到扩展中国剩余定理。


至于预处理剑…… 可以用 $\rm{STL}$ ,但是我选择用权值线段树。

还有一个问题,如果 $a_i\geq p_i$ 怎么办?

发现出题人很良心,对于所有的 $a_i\geq p_i$ 的情况,$p_i$ 都是等于 $1$ 的,这个时候直接求即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2e5+7;
const int V=1e6+7;

int Test,n,m,Mx,c[N],s[N<<1];
ll a[N],p[N],num[N],mod[N];

inline void Error() {puts("-1");return;}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x; 
}

struct Segment_tree {/*权值线段树*/
    #define mid ((l+r)>>1)
    int val[V<<2],right[V<<2];
    void update(int x,int l,int r,int pos,int op) {
        if(l==r) {val[x]+=op,right[x]=val[x]?l:0;return;}
        pos<=mid?update(x<<1,l,mid,pos,op):update(x<<1|1,mid+1,r,pos,op);
        right[x]=right[x<<1|1]?right[x<<1|1]:right[x<<1],val[x]=val[x<<1]+val[x<<1|1];
    }
    int findmin(int x,int l,int r) {
        if(l==r) return l;
        return val[x<<1]?findmin(x<<1,l,mid):findmin(x<<1|1,mid+1,r);
    }
    int findmax(int x,int l,int r) {
        if(l==r) return l;
        return val[x<<1|1]?findmax(x<<1|1,mid+1,r):findmax(x<<1,l,mid);
    }
    int query(int x,int l,int r,int pos) {
        if(l==r) return val[x]?l:0;int ans;
        if(pos<=mid) ans=query(x<<1,l,mid,pos);
        else {
            ans=right[x<<1];
            if(val[x<<1|1]) ans=max(ans,query(x<<1|1,mid+1,r,pos));
        }return ans;
    }
    void clear(int x,int l,int r) {
        val[x]=right[x]=0;if(l==r) return;
        clear(x<<1,l,mid),clear(x<<1|1,mid+1,r);
    }
}T;

namespace Math {
    ll mul(ll x,ll y,ll MOD) {
        x%=MOD,y%=MOD;ll res=0;
        for(;y;y>>=1,x=(x+x)%MOD) if(y&1) res=(res+x)%MOD;
        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),tmp=x;
        x=y,y=tmp-a/b*y;return gcd;
    }
    ll excrt(ll*v,ll*mod,int n) {
        ll M=mod[1],ans=v[1];
        for(int i=2;i<=n;++i) {
            ll a=M,b=mod[i],c=(v[i]-ans%b+b)%b;
            ll x,y,gcd=exgcd(a,b,x,y),lcm=b/gcd;
            // if(c%gcd) {Error();return -1;}
            x=mul(x,c/gcd,lcm),ans+=x*M,M*=lcm,ans=(ans%M+M)%M;
        }return (ans%M+M)%M;
    }
}using namespace Math;

inline void solve_clear() {
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    memset(a,0,sizeof(a));
    memset(p,0,sizeof(p));
    Mx=0;
}

inline void solve2() {/*特判情况*/
    ll ans=0;   
    for(int i=1;i<=n;++i)
        ans=max(ans,((a[i]+c[i]-1)/c[i]));
    printf("%lld\n",ans);
}
inline void solve() {
    IN(n),IN(m),solve_clear();
    bool flag=false;Mx=0;
    for(int i=1;i<=n;++i) IN(a[i]);
    for(int i=1;i<=n;++i) IN(p[i]),flag|=p[i]==1;
    for(int i=1;i<=n;++i) IN(s[m+i]),Mx=max(Mx,s[m+i]);
    for(int i=1;i<=m;++i) IN(s[i]),Mx=max(Mx,s[i]);
    T.clear(1,1,Mx);
    for(int i=1;i<=m;++i) T.update(1,1,Mx,s[i],1);
    for(int i=1;i<=n;++i) {
        int Mi=T.findmin(1,1,Mx);
        if(Mi>a[i]) c[i]=Mi;
        else if(a[i]>Mx) c[i]=T.findmax(1,1,Mx);
        else c[i]=T.query(1,1,Mx,a[i]);
        T.update(1,1,Mx,c[i],-1),T.update(1,1,Mx,s[m+i],1);
    }
    if(flag) {solve2();return;}
    for(int i=1;i<=n;++i) { /*为中国剩余定理做准备*/
        ll _x,_y,gcd=exgcd(c[i],p[i],_x,_y);
        if(a[i]%gcd) {Error();return;} 
        mod[i]=p[i]/gcd,_x=(_x%mod[i]+mod[i])%mod[i],num[i]=mul(a[i]/gcd,_x,mod[i]);
    }
    ll ans=excrt(num,mod,n);
    if(~ans) printf("%lld\n",ans);
}

int main() {
    IN(Test);
    while(Test--) solve();
    return 0;
}
分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

发表评论

电子邮件地址不会被公开。 必填项已用*标注