LOJ 2721「NOI2018」屠龙勇士

发表于 更新于 分类于

题目链接

因为是按照\(1-n\)的顺序杀龙，所以每次用的剑是固定的，可以先预处理出来。
每次需要满足
1 .\(atk*x\geq a-i\)
2. \(atk*x\equiv a-i\pmod {p-i}\)

观察数据，可以发现要不\(p-i\)满足\(a-i\leq p-i\)，要不\(p-i=1\)

对于第二种只需要刚好打到不大于\(0\)就可以了。

第一种情况，第一个限制显然是可以忽略的，因为满足第二个限制一定就满足第一种限制。

我们只需要考虑解出\(x\)，把每个方程都化为\(x\equiv r-i\pmod {m-i}\)这种一般形式。

直接的想法就是变成\(x\equiv a-i*inv(atk)\pmod{p-i}\)
但是模\(p-i\)意义下，\(atk\)的逆元不一定存在。
同余方程同时约去\(\gcd(a-i,p-i,atk)\)
如果\(\gcd(atk,p-i)\)仍不等于 \(1\)，则无解。

因为约去\(\gcd(a-i,p-i,atk)\) 后仍不互质，说明\(\gcd(atk,p-i)\nmid a-i\)，不满足翡蜀定理，则无解。

化完之后来解同余方程组就可以了。

细节没处理好，代码毒瘤。

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
115
116
#include <cstdio>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

#define int --int128 
const int N = 1e6 + 5;
int -, n, k, atk[N], nw[N];
int r[N], m[N];
int a[N], p[N];
bool pd = 1;
multiset<int> s;

int read() {
    int w = 0, f = 1; char ch = getchar();
    while(ch > '9' || ch < '0') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        w = w * 10 + ch - 48;
        ch = getchar();
    }
    return w * f;
}
void write(int x) {
    if(x < 0) {
        x = -x;
        putchar('-');
    }
    if(x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void prework() {
    for (int i = 1; i <= n; i++) {
		int res = 0;
        auto it = s.upper-bound(a[i]);
    	if (it == s.begin()) res = *it;
        else res = *(--it);
    	s.erase(it);
    	atk[i] = res;
		s.insert(nw[i]);
	}
}
int mul(int a, int b, int p) {
	a = (a % p + p) % p;
    b = (b % p + p) % p;	
	return (a * b % p + p) % p;
	/*assert(a >= 0); assert(b >= 0);
    int res = 0;
	for (; b; b >>= 1, a = (a + a) % p) if (b & 1) res = (res + a) % p;
	return res;*/
}

int solve1() {
    int res = 1;
	for (int i = 1; i <= n; i++) 
        res = max(res, (a[i] + atk[i] - 1) / atk[i]);
	return res;
}

void exgcd(int a, int b, int& d, int& x, int& y) {
	if(b == 0) {d = a, x = 1, y = 0; return;}
	exgcd(b, a % b, d, y, x); y -= x * (a / b);
}
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
int China() {
    int M = m[1], R = r[1];
    for(int i = 2; i <= n; i++) {
    	int a = M, b = m[i], c = r[i] - R, x, y, d;
    	exgcd(a, b, d, x, y);
    	if(c % d != 0) return -1;
        x = (mul(x, c / d, b) + b) % b;
        R += x * M, M *= m[i] / d, R = (R + M) % M;
    }
    return R;
}
int inv(int a, int p) {
	int d, x, y;
	exgcd(a, p, d, x, y);
	return (x % p + p) % p;
}

bool build() {
	int d;
	for (int i = 1; i <= n; i++) {
	    d = gcd(atk[i], p[i]); d = gcd(d, a[i]);
	   	atk[i] /= d, p[i] /= d, a[i] /= d;
		if (gcd(atk[i], p[i]) != 1) return 0;
		m[i] = p[i], r[i] = mul(a[i], inv(atk[i], p[i]), p[i]);
	}
	return 1;
}

signed main() {
	freopen("dragon.in", "r", stdin);
    freopen("dragon.out", "w", stdout);
	for ( - = read(); -; ---) {
	    s.clear();
	    pd = 1;	
		n = read(), k = read();
		for (int i = 1; i <= n; i++) a[i] = read();
		for (int i = 1; i <= n; i++) {p[i] = read(); if (p[i] != 1) pd = 0;}
		for (int i = 1; i <= n; i++) nw[i] = read();
		for (int i = 1, x; i <= k; i++) x = read(), s.insert(x);
		prework();
		if (pd == 1) {write(solve1()); puts("");continue;}
		if (!build()) {puts("-1"); continue;}
		write(China());
		puts("");
	}
	return 0;
}