「NOI2018」屠龙勇士题解

传送门

题目大意

输入格式

输出格式

数据范围

样例解释

题解

因为每次巨龙面对的剑是可以确定的

所以设$g_i$表示第$i$只龙面对的剑的攻击力

容易发现$a_i-g_i x \equiv 0 \pmod{p_i}$

移项得$g_i x \equiv a_i \pmod{p_i}$​

也就是$x \equiv a_i \times g_i^{-1} \pmod{p_i}$

$g_i^{-1}$是$g_i$​的逆元

根据模运算的消去律

柿子可以转成酱紫：$x \equiv \frac{a_i}{d} \times (\frac{g_i}{d})^{-1} \pmod{\frac{p_i}{d}}$

其中$d=gcd(a_i,g_i,p_i)$

因为$p_i$不一定是素数，所以不能用费马小定理

可以用扩展欧几里得（$exgcd$）

然鹅$\frac{g_i}{d}$与$\frac{p_i}{d}$必须互质，否则前者没有逆元，即无解，输出-1

然后我们会得到一堆类似$x \equiv c_i \pmod{p_i}$的柿子

用扩展中国剩余定理两两合并，举个栗子（摘自OI-WiKi）

设两个方程$x \equiv a_1 \pmod{p_1}$，$x \equiv a_2 \pmod{p_2}$

将它们转化成不定方程：$x=p_1r+a_1=p_2s+a_2$，其中$r,s$是整数，则有$p_1r-p_2s=a_2-a_1$

由裴蜀定理，当$a_2-a_1$不能被$gcd(m_1,m_2)$整除时，无解，输出-1

其他情况下，可以通过扩展欧几里得算法解出来一组可行解：$(p,q)$

则原来的两方程组成的模方程组的解为 $x \equiv b \pmod M$，其中$b=m_1p+a_1,M=lcm(m_1,m_2)$

最后得出$x \equiv res \pmod {LCM}$​

另外，由于两个long long一起乘会炸，所以请使用龟速快速乘

回到前面，如何在$O(n\;log\;n)$的时间复杂度内找出$g_i$？

可以用线段树，但是——

有现成的$multiset$，为何放着不用呢？

此处不多介绍，自己上网查找

$P.s:$不知道是因为我写丑了还是什么原因，跑的贼慢，大佬勿喷

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <set>
#include <cstdio>
#define N 1000005
#define ll long long
#define int64 long long
#define mulit multiset<ll>::iterator
using namespace std;
ll i,T,n,m,a[N],g[N],p[N],r[N],mx;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if (!b) return x=1,y=0,a;
	ll d=exgcd(b,a%b,x,y);
	ll t=x;x=y,y=t-(a/b)*y;
	return d;
}ll gcd(ll a,ll b) {
	if (!b) return a;
	return gcd(b,a%b);
}int64 inv(int64 a,int64 b) {
	int64 x,y;exgcd(a,b,x,y);
	return x;//ax-by=1
}int64 mul(ll a,ll b,ll mo,ll res=0,bool f=0)
{
	if (b<0) f=1,b=-b;
	for (;b;b>>=1,a=(a+a)%mo) {
		if (b&1) res=(res+a)%mo;
	}return (f)?-res:res;
}int64 excrt(int64 &res)
{
	ll lcm=1;res=0;
	for (int i=1;i<=n;++i)
	{
		ll d1=gcd(a[i],gcd(g[i],p[i]));
		a[i]/=d1,g[i]/=d1,p[i]/=d1;
		if (gcd(g[i],p[i])>1) return res=-1,1;
		ll y=mul(a[i],inv(g[i],p[i]),p[i])+p[i];y%=p[i];
		ll c=y-res,r,s,d=gcd(lcm,p[i]);
		if (c%d) return res=-1,1;
		exgcd(lcm/d,p[i]/d,r,s);
		ll t1=mul(c/d,lcm,lcm/d*p[i]);
		ll t2=mul(t1,r,lcm/d*p[i]);
		res+=t2,lcm=lcm/d*p[i];
		res%=lcm,res+=lcm,res%=lcm;
	}return lcm;
}multiset<int64> h;
int main()
{
	scanf("%lld",&T);
	while (T--)
	{
		h.clear(),mx=0;scanf("%lld%lld",&n,&m);
		for (i=1;i<=n;++i) scanf("%lld",a+i);
		for (i=1;i<=n;++i) scanf("%lld",p+i);
		for (i=1;i<=n;++i) scanf("%lld",r+i);
		for (i=1;i<=m;++i) {
			ll x;scanf("%lld",&x);
			h.insert(x);
		}for (i=1;i<=n;++i) {
			mulit it=h.upper_bound(a[i]);
			if (it!=h.begin()) --it;
			g[i]=*it,h.erase(it);
			mx=max(mx,(a[i]+g[i]-1)/g[i]);
			h.insert(r[i]);
		}int64 x,lcm=excrt(x);
		if (x!=-1 && x<mx)
			x+=(mx-x+lcm-1)/lcm;
		printf("%lld\n",x);
	}
}