[洛谷 4774,loj 2721][NOI2018]屠龙勇士

题目链接

https://www.luogu.com.cn/problem/P4774

https://loj.ac/problem/2721

题解

首先,根据题意,我们可以很容易预处理出面对第 \(i\) 条龙时使用的剑,记其伤害值为 \(c_i\)。

做完了这样一步预处理过后,会发现我们实际上要解若干个形如 \(c_ix\equiv a_i \pmod{p_i}\) 这样的同余方程组联立后的最小解。

解这样的方程组,第一个前提条件是 \(a_i \leq p_i\),如果不满足这个条件的话,可能会出现龙的血量在 \(\bmod\ p_i\) 意义下为零,但实际血量不为零的问题。

不过好在不满足 \(a_i \leq p_i\) 的测试数据都满足 \(p_i=1\),这意味着这种情况下的答案将直接为 \(\max \left \lceil \frac{a_i}{c_i} \right \rceil\)。

排除这种情况后,我们下面的讨论均在 \(a_i \leq p_i\) 的前提下进行。

这个方程组看起来像是可以应用扩展中国剩余定理(ExCRT)的样子。但是 ExCRT 要求 \(x\) 前面的系数必须为 \(1\)。

将方程组两边同时除 \(c_i\)?不行,模 \(p_i\) 意义下 \(c_i\) 的逆元不一定存在。

考虑将线性同余方程改写成不定方程的形式。

像 \(c_ix\equiv a_i \pmod{p_i}\) 就可以改写为:\(c_ix+p_iy=a_i\)。

接下来用扩展欧几里得算法来解这个方程组即可。

等等!扩展欧几里得算法解的是形如 \(ax+by=\gcd(a,b)\) 形式的不定方程,上面的方程显然不满足这个形式,不能直接用 exgcd 来解。

换个元后稍微推一下:

我们设 \(x=\frac{a_i}{\gcd(c_i,p_i)}x’\),\(y=\frac{a_i}{\gcd(c_i,p_i)}y’\)。

则原来的方程可以改写为:

$$
c_ix’+p_iy’=\gcd(c_i,p_i)
$$

现在方程变成了标准形式,可以直接解了。

设上面方程的一组解是 \(x’=x’_0\),\(y’=y’_0\),则原方程与之对应的解为 \(x_0=\frac{a_i}{\gcd(c_i,p_i)}x’_0\),\(y_0=\frac{a_i}{\gcd(c_i,p_i)}y’_0\)。

这是一个方程组的解,对于多个方程组,我们需要用 ExCRT(本质上还是扩展欧几里得)来合并它们。

简单来说,对于两个线性同余方程:

$$
\begin{cases}
x \equiv a_1 \pmod {p_1}\\
x \equiv a_2 \pmod {p_2}\\
\end{cases}
$$

我们还是把它们改写成不定方程的形式:

$$
\begin{cases}
x = a_1 +p_1y_1\\
x = a_2 +p_2y_2\\
\end{cases}
$$

联立后消去 \(x\),用扩展欧几里得解 \(y_1,y_2\) 即可合并两个方程。

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
long long a[100005],p[100005];
long long nswd[100005],c[100005];
multiset<long long> swd;
int n,m;
long long exgcd(long long a,long long b,long long&x,long long&y)
{
 if(b==0)
 {
  x=1,y=0;
  return a;
 }
 long long g=exgcd(b,a%b,x,y);
 int t=x;
 x=y;
 y=t-a/b*y;
 return g;
}
long long mul(long long x,long long y,long long p)
{
 long long ans=0;
 while(y)
 {
  if(y&1)ans=(ans+x)%p;
  x=(x+x)%p;
  y>>=1;
 }
 return ans;
}
namespace sub1//p_i maybe greater than a_i, but guaranteed p_i=1
{
 bool check()
 {
  bool flag=true;
  for(int i=1;i<=n;i++)
   flag&=(p[i]==1);
  return flag;
 }
 void solve()
 {
  long long ans=0;
  for(int i=1;i<=n;i++)
   ans=max(ans,(long long)((a[i]/c[i])+(a[i]%c[i]!=0)));
  cout<<ans<<endl;
 }
}
int main()
{
 ios::sync_with_stdio(false);
 int t;
 cin>>t;
 while(t--)
 {
  bool flag=true;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
   cin>>a[i];
  for(int i=1;i<=n;i++)
   cin>>p[i];
  for(int i=1;i<=n;i++)
   cin>>nswd[i];
  swd.clear();
  for(int i=1;i<=m;i++)
  {
   long long x;
   cin>>x;
   swd.insert(x);
  }
  for(int i=1;i<=n;i++)
  {
   auto it=swd.upper_bound(a[i]);
   if(it!=swd.begin())it--;
   c[i]=*it;
   swd.erase(it);
   swd.insert(nswd[i]);
  }
  long long ans=0,z=1;
  if(sub1::check())
  {
   sub1::solve();
   continue;
  }
  for(int i=1;i<=n;i++)
  {
   c[i]%=p[i],a[i]%=p[i];
   if(!c[i]&&a[i])
   {
    cout<<-1<<endl;
    flag=false;break;
   }
   if(!c[i]&&!a[i])continue;
   long long x,y;
   long long g=exgcd(c[i],p[i],x,y);
   if(a[i]%g)
   {
    cout<<-1<<endl;
    flag=false;break;
   }
   p[i]/=g;
   a[i]=mul(a[i]/g,(x%p[i]+p[i])%p[i],p[i]);
   g=exgcd(z,p[i],x,y);
   if((a[i]-ans)%g)
   {
    cout<<-1<<endl;
    flag=false;break;
   }
   z=z/g*p[i];
   ans=(ans+mul(mul(z/p[i],((a[i]-ans)%z+z)%z,z),(x%z+z)%z,z))%z;
  }
  if(flag)cout<<ans<<endl;
 }
 return 0;
}

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据