题目描述

小D 最近在网上发现了一款小游戏。游戏的规则如下：

游戏的目标是按照编号1~n 顺序杀掉n 条巨龙，每条巨龙拥有一个初始的生命 值ai 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每 次增加 pi ，直至生命值非负。只有在攻击结束后且当生命值恰. 好. 为 0 时它才会 死去。

游戏开始时玩家拥有m 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一 把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。 小D 觉得这款游戏十分无聊，但最快通关的玩家可以获得ION2018 的参赛资格， 于是小D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻. 击. 力. 最. 低. 的一把剑作为武器。

机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固. 定. 的. x 次，使巨龙的生命值减少 x×ATKx \times ATKx×ATK 。

之后，巨龙会不断使用恢复能力，每次恢复pi 生命值。若在使用恢复能力前或 某一次恢复后其生命值为0 ，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数x 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出-1 即可。

输入输出格式

输入格式：

从文件dragon.in 中读入数据。

第一行一个整数T ，代表数据组数。

接下来T 组数据，每组数据包含5 行。

每组数据的第一行包含两个整数，n 和m ，代表巨龙的数量和初始剑的数量;接下来一行包含n 个正整数，第i 个数表示第i 条巨龙的初始生命值ai ;接下来一行包含n 个正整数，第i 个数表示第i 条巨龙的恢复能力pi ;接下来一行包含n 个正整数，第i 个数表示杀死第i 条巨龙后奖励的剑的攻击力;接下来一行包含m 个正整数，表示初始拥有的m 把剑的攻击力。

输出格式：

输出到文件dragon.out 中。 一共T 行。

第i 行一个整数，表示对于第i 组数据，能够使得机器人通关游戏的最小攻击次数x ，如果答案不存在，输出-1。

---

题解

这题细节巨多，考场上过了大样例就没管。。结果挂成45分。

1. x和p不互质，不能求逆元？？？所以直接用带参数的同余方程 \[b_ix\equiv a_i\mod p_i\] 令\(g=gcd(b_i,p_i),x_0\)为该方程的一个特解，则最后\(x_0\)一定要模\(p_i/g\)而不是直接模\(p_i\)
2. 数据范围是\(10^{12}\)直接用\(long\ long\)的话，中间结果可能会爆炸，所以要拆开来乘。
3. 注意取最小正整数

#include
    
     #define REP(i,a,b) for(int i=(a);i<=(b);++i)#define DEC(i,a,b) for(int i=(a);i>=(b);--i)#define dbg(...) fprintf(stderr,__VA_ARGS__)using namespace std;template
     
       inline bool smax(T&x,const U&y){return y>x?(x=y,1):0;}template
      
        inline bool smin(T&x,const U&y){return y
       
         pii;#define pb push_back#define X first#define Y secondtemplate
        
         inline void rd(T&w){    char c;    while(!isdigit(c=getchar()));w=c-48;    while(isdigit(c=getchar()))w=w*10+c-48;}const int N=2e5+5;int n,m;ll a[N],p[N],b[N],minx,tmp;inline ll mul(ll x,ll y,ll p){    if(x>=p)x%=p;if(y>=p)y%=p;    if(x<=1e9&&y<=1e9)return x*y%p;    ll ans=0,tmp;    while(y){        if(tmp=y%10000)ans=(ans+x*tmp%p)%p;        x=x*10000%p;y/=10000;    }    return ans;}inline ll gcd(ll a,ll b,ll&x,ll&y){    if(!b)return x=1,y=0,a;    ll d=gcd(b,a%b,y,x);y-=a/b*x;    return d;}inline void write(ll x){    static char st[25];    int top=0;    while(x)st[++top]=x%10+'0',x/=10;    while(top)putchar(st[top--]);    putchar('\n');}multiset
         
           s;multiset
          
           ::iterator it;int main(){// freopen("dragon.in","r",stdin);// freopen("dragon.out","w",stdout); int T;rd(T); while(T--){ rd(n),rd(m);s.clear();minx=0; REP(i,1,n)rd(a[i]); REP(i,1,n)rd(p[i]); REP(i,1,n)rd(b[i]); REP(i,1,m)rd(tmp),s.insert(tmp); ll x,y; REP(i,1,n){ it=s.upper_bound(a[i]);if(it!=s.begin())--it; smax(minx,(a[i]-1)/(*it)+1);a[i]%=p[i]; s.insert(b[i]); b[i]=*it; s.erase(it); } ll g=gcd(b[1],p[1],x,y),k,now; bool f=1; if(a[1]%g)f=0;else now=mul(a[1]/g,x,k=p[1]/g); if(f)REP(i,2,n){ ll&m=p[i]; g=gcd(k%m*b[i]%m,m,x,y); a[i]=(a[i]-b[i]*now%m+m)%m; if(a[i]%g){f=0;break;} tmp=m/g;x=mul(a[i]/g,x,tmp); now+=x*k;k*=tmp; now=(now%k+k)%k; } if(f){ now=minx/k*k+now; write(now>=minx?now:now+k); }else puts("-1"); } return 0;}