NOI2018 屠龙勇士
\(\text{Analysis}\)
这题怎么做非常明显
依照关卡循环,然后利用数据结构维护当天用的剑(如权值线段树或平衡树,建议 \(set\))
通过一元同余方程解出当前关卡的答案(没有或有无数个,用通解表示)
把每个关卡答案的通解联立起来,就有了一堆同余方程组
扩展中国剩余定理求解即可
注意无解情况的判断(即解方程时)
\(\text{Code}\)
#include
#include
#define LL long long
using namespace std;
const int N = 1e5 + 5, Len = 1e6;
int n, m;
LL a[N], p[N], atk[N], tk[N];
inline void read(LL &x)
{
x = 0; LL f = 1; char ch = getchar();
while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9') x = (x<<3)+(x<<1) + ch - '0', ch = getchar();
x *= f;
}
int seg[N << 5], ls[N << 5], rs[N << 5], size, rt;
void update(int &p, int l, int r, int x, int v)
{
if (!p) p = ++size, ls[p] = rs[p] = seg[p] = 0;
seg[p] += v;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) update(ls[p], l, mid, x, v);
else update(rs[p], mid + 1, r, x, v);
}
int query_mi(int p, int l, int r, int x)
{
if (!seg[p]) return 0;
if (l == r) return l;
int mid = (l + r) >> 1, res = 0;
res = query_mi(ls[p], l, mid, x);
if (res) return res;
if (x > mid) return query_mi(rs[p], mid + 1, r, x);
}
int query_mx(int p, int l, int r, int x)
{
if (!seg[p]) return 0;
if (l == r) return l;
int mid = (l + r) >> 1, res = 0;
if (x > mid) res = query_mx(rs[p], mid + 1, r, x);
if (res) return res;
return query_mx(ls[p], l, mid, x);
}
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b){x = 1, y = 0; return a;}
LL d = exgcd(b, a % b, x, y);
LL tmp = x; x = y, y = tmp - (a / b) * y;
return d;
}
LL fmul(LL x, LL y, LL P)
{
LL ret = 0;
x %= P, y %= P;
if (y < 0) y = (y + P) % P;
for(; y; y >>= 1)
{
if (y & 1) ret = (ret + x) % P;
x = x * 2 % P;
}
return ret;
}
LL exCRT(LL down)
{
LL A = a[1], P = p[1], M, x, y, d, c;
for(int i = 2; i <= n; i++)
{
d = exgcd(P, p[i], x, y);
if ((a[i] - A) % d) return -1LL;
c = p[i] / d, x = (fmul(x, (a[i] - A) / d, c) + c) % c;
M = P / d * p[i], A = (fmul(x, P, M) + A) % M, P = M;
}
if (A < down) A += ((down - x - 1) / M + 1) * M;
return A;
}
inline LL solve()
{
rt = size = 0;
for(register int i = 1; i <= m; i++) update(rt, 1, Len, atk[i], 1);
LL A, c, x, y, d, knf = -1;
for(register int i = 1; i <= n; i++)
{
A = query_mx(rt, 1, Len, min(a[i], (LL)Len));
if (!A) A = query_mi(rt, 1, Len, Len);
if (p[i] == 1)
{
knf = max((a[i] - 1) / A + 1, knf), a[i] = 0, p[i] = 1;
update(rt, 1, Len, A, -1), update(rt, 1, Len, tk[i], 1);
continue;
}
if (a[i] && A % p[i] == 0) return -1LL;
d = exgcd(A, p[i], x, y);
if (a[i] % d) return -1LL;
c = p[i] / d;
a[i] = x = (fmul(x, a[i] / d, c) + c) % c, p[i] /= d;
update(rt, 1, Len, A, -1), update(rt, 1, Len, tk[i], 1);
}
return exCRT(knf);
}
int main()
{
int T; scanf("%d", &T);
for(; T; --T)
{
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i++) read(a[i]);
for(register int i = 1; i <= n; i++) read(p[i]);
for(register int i = 1; i <= n; i++) read(tk[i]);
for(register int i = 1; i <= m; i++) read(atk[i]);
printf("%lld\n", solve());
}
}