题面

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

解析

\(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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #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
           
            s;multiset
            
             ::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
             
              >=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]