Fork me on GitHub

「NOI2018」屠龙勇士 CRT,EXCRT

发表于 | 分类于
字数统计: 1,431字 | 阅读时长 ≈ 7分钟

一道细节毒瘤的签到题

题意

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

  • 游戏的目标是按照编号$1 - n$ 顺序杀掉 $n$ 条巨龙，每条巨龙拥有一个初始的生命值 $a_i$ 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$ ,直至生命值非负。只有在攻击结束后且当生命值恰好为 $0$ 时它才会死去。
  • 游戏开始时玩家拥有 $m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。 小D觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小D决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
  • 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
  • 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的$x$次，使巨龙的生命值减少 $x \times ATK$ 。
  • 之后，巨龙会不断使用恢复能力，每次恢复pi 生命值。若在使用恢复能力前或 某一次恢复后其生命值为0 ，则巨龙死亡，玩家通过本关。

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

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

思路

不难发现 每次使用的剑都是可以确定的

用priority_queue或者map或者set或者脑残地手写一个平衡树都可以在$logn$的时间内得到.

所以用$O(nlogn)$的时间得到所有的$swd_i,p_i,a_i$

我们的任务是解对于所有模方程组成立的 $x$.

似乎用一个EXCRT就好了,因为不保证$p_i$是质数,要用ex_gcd求逆元,特判负数情况.

如果用乘起来的CRT秒秒钟爆炸long long哦 用合并式的EXCRT似乎更加资瓷哦

中间爆long long导致我同步赛就只有25分了….炒鸡难受…

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 2e5+100;
///------------------head------------------
int a[MAXN],p[MAXN],swd[MAXN],tag[MAXN],cur=1,cc;
int Remain[MAXN];
inline int MulMod(int a,int b,int m){
    int t = a * b - (int)((long double) a * b /m) *m;
    return t%m+(t>>63&m);
}
struct Node{
    int pri,atk;
    bool operator < (const Node &b) const {
        if (pri < cur && b.pri < cur){
            if(atk <= cc && b.atk <= cc) return atk < b.atk;
            else return atk > b.atk;
        }
        else return pri < b.pri;
    }
    Node(int xx=0,int yy=0):pri(xx),atk(yy){}
}b[MAXN];
priority_queue<Node>pq;
int n,m;
void Pref(){
    while(!pq.empty()) pq.pop();
    cur=1; cc=0;
}
int exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return a;}int k=exgcd(b,a%b,y,x);y-=x*(a/b); return k;}
inline int exgcd_inv(int a,int b){ //calc inv(a) in mod b
    int x,y,ans;
    if (exgcd(a,b,x,y) == 1) ans = (x%b+b) % b;
    else ans = -1;
    return ans;
}
inline bool merge(int a1, int m1, int a2, int m2, int &a3, int &m3)  {
    int d = __gcd(m1, m2);
    int c = a2 - a1;
    if(c % d) return false;
    c = (c % m2 + m2) % m2;
    m1 /= d;m2 /= d;c /= d;
    c = MulMod(c,exgcd_inv(m1, m2),m2);
    c *= m1 * d; c += a1;
    m3 = m1 * m2 * d;
    a3 = (c % m3 + m3) % m3;
    return true;
}
int CRT(int a[], int m[], int n)  {
    int a1 = a[1];
    int m1 = m[1];
    for(int i=2; i<=n; i++)  {
        int a2 = a[i];
        int m2 = m[i];
        int m3, a3;
        if(!merge(a1, m1, a2, m2, a3, m3))
            return -1;
        a1 = a3;
        m1 = m3;
    }
    return (a1 % m1 + m1) % m1;
}

signed main(signed argc, char *argv[]){
    freopen("dragon.in","r",stdin);
    freopen("dragon.out","w",stdout);
    int T=read();
    while(T--){
        int flg=0,minans=0;
        Pref();
        n=read(); m=read();
        rep(i,1,n) a[i]=read();rep(i,1,n) p[i]=read();
        rep(i,1,n) b[i]=Node(i,read());rep(i,1,m) b[n+i] = Node(0,read());
        rep(i,1,m) pq.push(b[n+i]);
        rep(i,1,n){
            cur=i;
            cc=a[cur];
            Node t=pq.top();
            swd[i]=t.atk;
            pq.pop();
            pq.push(b[i]);
            minans = max(minans,((a[i]+swd[i]-1)/swd[i]));
        }
        rep(i,1,n) {
            int iv = exgcd_inv(swd[i],p[i]);
            if (iv == -1) {flg = 1; break;}
            Remain[i] = MulMod(iv,a[i],p[i]); //iv * a[i] % p[i];
        }
        if (flg) {puts("-1"); continue;}
        int ans = CRT(Remain,p,n);
        if (ans == -1) puts("-1");
        else printf("%lld\n",max(ans,minans));
    }
    fclose(stdin); fclose(stdout);
    return 0;
}