[NOI2018]屠龙勇士

数论

题面

咕咕咕，直接概括题意就没意思了，戳我

解析

$20pts:n=10^5,m=1,p_i=1$

一是明确了用哪把剑刺恐龙，而且$p_i=1$意味着只要把血量打到$0$及以下即可。
$O(n)$取刺杀每只恐龙的最大时间。
注意无条件向上取整。（可以用$ceil$，也可以$(ans+mod-1)\%mod$)

il void solve1()
{
  re ll now=atk[1],mn=-1e18;
  fp(i,1,n)
    {
      mn=max(mn,ceil(1.0*a[i]/now));
      now=b[i];
    }
  printf("%lld\n",mn);
}

$35pts:n\leq10^3,m\leq10^3,p_i\leq10^5$

$m>1$就要预处理用哪个剑刺一条龙的了。
$m\leq10^3$对我这种不太会用$set$的蒟蒻还是很良心的，可以二分出是哪个剑，还可以用插入排序来加入或删除数。
预处理复杂度直达$O(n^2)$。

注意到这一档数据有个独特性质：$lcm(p_i)\leq10^6$。
手玩了几组数据，发现$ans$一定比$lcm(p_i)$小。
于是直接爆枚 刺龙次数 到$10^6$。
什么，你怕$TLE$？怕$O(10^6n)$爆炸？

• 可以预处理出时间的下限（把每条龙打到负血）
• 一旦一条龙刺不死就$break$
• 一旦找到答案就可以$return$

il int find(re int x)
{
  re int l=1,r=m,ans=1;
  while(l<=r)
    {
      re int mid=l+r>>1;
      if(atk[mid]<=x) ans=mid,l=mid+1;
      else r=mid-1;
    }
  return ans;
}
il void solve3()
{
  fp(i,1,n)
    {
      re int x=find(a[i]);
      ying[i]=atk[x];
      fp(j,x,m-1) atk[j]=atk[j+1];
      re int ppl=find1(b[i]);
      fq(j,m,ppl+1) atk[j]=atk[j-1];
      atk[ppl]=b[i];
    }
  re ll mn=-1e18;
  fp(i,1,n) mn=max(mn,(ceil(1.0*a[i]/ying[i])));
  fp(i,mn,1000000)
    {
      re int ppl=1;
      fp(j,1,n) if((i*ying[j]-a[j])%p[j]!=0) {ppl=0;break;}
      if(ppl) {printf("%d\n",i);return;}
    }
  puts("-1");
}

$65pts:n=1,m=1,p_i\leq10^8$

意思是只要我们在不暴枚的前提下解一个方程$(atk[1]*x-a_i)\%p_i=0$
有模号？化成同余方程形式$atk[1]*x-a_i\equiv 0(mod\ p_i)$
这种方程解不得，继续化。
$atk[1]*x\equiv a_i(mod\ p_i)$
然后发现了性质$a_i\leq p_i$的用途。。。

这就是同余方程的经典模型$Ax\equiv B(mod\ M)$,不记得就去看专项总结关于同余方程解法。

il void exgcd(re ll A,re ll B,re ll &D,re ll &x,re ll &y,re ll c)
{
  if(!B) x=1,y=0,D=A;
  else exgcd(B,ok(A,B),D,y,x,c),y-=(A/B)*x;
}
il void solve2()
{
  re ll A=atk[1],B=a[1],M=p[1],D,x,y,ysn,zsy;
  exgcd(A,M,D,x,y,B);
  if(B%D) {puts("-1");return;}
  ysn=B/D,zsy=M/D;
  x=ok((ok(x*ysn,zsy)+zsy),zsy);
  //x=ok(x,zsy);
  printf("%lld\n",x);
}

$75pts:n=10^5,m=10^5,p_i=1$

又不要解方程了。
这档数据专门卡逗逼的$O(n^2)$预处理。

它要求一种数据结构，能二分查找，能删除，能插数，能自动排序。
然后我想起来了平衡树。。。

$set$神器了解一下，有了它，这一档根本就没多少码量。

il void solve4()
{
    s.clear();
    fp(i,1,m) s.insert(atk[i]);
    fp(i,1,n)
    {
      it=s.lower_bound(a[i]);
            if(it!=s.begin()) --it;
            ying[i]=*it;
            s.erase(it);s.insert(b[i]);
    }
  re ll mn=-1e18;
  fp(i,1,n) mn=max(mn,ceil(1.0*a[i]/ying[i]));
  printf("%lld\n",mn);
}

$100pts$算法

拓展中国剩余定理专门用来解多个同余方程。
而这题好像是个板子。
还是专项总结关于同余方程解法。
然而我犯了$n$个细节错误：

• 判断是否无解可在$exgcd$以后判，直接$exgcd$会解出实数
• 两个$long\ long$数不能直接相乘，会炸；要乘只能用龟速乘（复杂度多个$log$，但好处是可以边乘边取模）

il ll mul(re ll x,re ll y,re ll mod)
{
  if(y<0)x=-x,y=-y;//!!!!!!
  re ll S=0,n=y,T=x;
  while(n)
    {
      if(n&1) (S+=T)%=mod;
      (T+=T)%=mod;
      n>>=1;
    }
  return S;
}

• 用龟速乘要小心后一个数是负数！！！
• 没事不要用龟速模，会卡死

il ll ok(re ll x,re ll y){while(x<0) x+=y;while(x>=y) x-=y;return x;}

• 拓展中国剩余定理合并方程时模的是$lcm$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
int T;
ll n,m,a[N],p[N],b[N],atk[N],ying[N],ysn[N];
multiset<ll>s;
multiset<ll>::iterator it;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re ll x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+48);
}
il void exgcd(re ll A,re ll B,re ll &D,re ll &x,re ll &y)
{
  if(!B) x=1,y=0,D=A;
  else exgcd(B,A%B,D,y,x),y-=(A/B)*x;
}
il ll gcd(re ll x,re ll y){if(x<y) swap(x,y);if(!y) return x;else return gcd(y,x%y);}
il ll lcm(re ll x,re ll y){return x/gcd(x,y)*y;}//!!!!!!
il ll mul(re ll x,re ll y,re ll mod)
{
  if(y<0)x=-x,y=-y;//!!!!!!
  re ll S=0,n=y,T=x;
  while(n)
    {
      if(n&1) (S+=T)%=mod;
      (T+=T)%=mod;
      n>>=1;
    }
  return S;
}
il void solve()
{
  s.clear();
  fp(i,1,m) s.insert(atk[i]);
  fp(i,1,n)
  {
    it=s.lower_bound(a[i]+1);
    if(it!=s.begin()) --it;
    ying[i]=*it;
    s.erase(it);s.insert(b[i]);
  }
  fp(i,1,n)
    {
      re ll A=ying[i],B=a[i],M=p[i],D,x,y;
        exgcd(A,M,D,x,y);
    if(B%D) {puts("-1");return;}
    x=mul(x,B/D,M/D);
        ysn[i]=x;p[i]/=D;
    }   
  fp(i,2,n)
    {
        re ll A=p[i-1],B=ysn[i]-ysn[i-1],M=p[i],D,x,y;
        re ll L=lcm(p[i-1],p[i]);
        exgcd(A,M,D,x,y);
        if(B%D){puts("-1");return;}//!!!!!!
        x=mul(B/D,x,L);
        ysn[i]=ysn[i-1]+mul(x,p[i-1],L);//!!!!!!
        ysn[i]=(ysn[i]%L+L)%L;
        p[i]=L;
    }   
  re ll ans=ysn[n];
  fp(i,1,n) if(ans*ying[i]<a[i]) ans+=(((a[i]-ans*ying[i]+ying[i]-1)/ying[i]+p[n]-1)/p[n]*p[n]);
  wri(ans);putchar('\n');
}
int main()
{
  T=gi();
  while(T--)
  {
    n=gi();m=gi();
    fp(i,1,n) a[i]=gi();fp(i,1,n) p[i]=gi();
    fp(i,1,n) b[i]=gi();fp(i,1,m) atk[i]=gi();sort(atk+1,atk+1+m);
    solve();
  }
  return 0;
}