咕咕来更博了 (￣︶￣*))
发现每一条龙对应的剑是可以预处理的…… 设第 $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;
}
0 条评论