【题解】LOJ 2721 「NOI2018」屠龙勇士

Problem

题目链接

Thought

首先,对于每只巨龙,可以简单的算出使用哪把剑

然后,需要算出最小的 $x$ ,满足:

$$ a_i-x*ATK_i\equiv p_i\\ a_i\leq x*ATK_i\ $$

变形:

$$ a_i\equiv x*ATK_i \mod p_i\\ a_i\leq x*ATK_i $$

求出第一部分的通解,需要使用 扩展CRT

然后算出能够使得 $a_i\leq x*ATK_i$ 的最小次数即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef multiset<ll> ms;
const int N = 100010;
ll n, m, a[N], p[N], hur[N], s[N], b[N], TTT;

ms S;
ms ::iterator it;

ll read();
void init();

ll gcd(ll, ll);
ll exgcd(ll, ll, ll &, ll &);
ll inv(ll, ll);
ll qtime(ll, ll, ll);
void CRT();

int main() {
    freopen("dragon.in", "r", stdin);
    freopen("dragon.out", "w", stdout);
    TTT = read();
    while (TTT--) {
        init();
        CRT();
    }
    return 0;
}

ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {x = 1; y = 0; return a;}
    ll tmp = exgcd(b, a % b, x, y);
    ll t = x; x = y; y = t - a / b * y;
    return tmp;
}
ll inv(ll a, ll b) {
    ll x, y;
    exgcd(a, b, x, y);
    x = (x % b + b) % b;
    if (!x)
        x += b;
    return x;
}
void CRT() {
    bool flag = 1;
    ll m1, m2, c1, c2;
    for(int i = 2; i <= n; ++i) {
        m1 = p[i - 1]; m2 = p[i];
        c1 = a[i - 1]; c2 = a[i];
        ll t = gcd(m1, m2);
        if ((c2 - c1) % t != 0) {
            flag = 0;
            break;
        }
        p[i] = m1 / t * m2;
        a[i] = qtime(qtime(inv(m1 / t, m2 / t), (c2 - c1) / t, m2 / t), m1, p[i]) + c1;
        a[i] = (a[i] % p[i] + p[i]) % p[i];
    }
    if (!flag)
        puts("-1");
    else {
        if (!a[n])
            a[n] += p[n];
        double maxn = 0;
        for(int i = 1; i <= n; ++i)
            if ((double)b[i] / ((double)a[n] * (double)s[i]) >= maxn)
                maxn = (double)b[i] / ((double)a[n] * (double)s[i]);
        a[n] = a[n] * ceil(maxn);
        printf("%lld\n", a[n]);
    }
}
ll qtime(ll A, ll B, ll C) {
    ll ANS = 0, FLAG = 1;
    if (A < 0)
        FLAG = - FLAG, A = - A;
    if (B < 0)
        FLAG = - FLAG, B = - B;
    A %= C; B %= C;
    while (B) {
        if (B & 1)
            ANS = (ANS + A) % C;
        A = (A + A) % C;
        B >>= 1;
    }
    ANS = (ANS * FLAG % C + C) % C;
    return ANS;
}
void init() {
    S.clear();
    n = read(); m = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        b[i] = a[i];
    }
    for(int i = 1; i <= n; ++i) p[i] = read();
    for(int i = 1; i <= n; ++i) hur[i] = read();
    for(int i = 1; i <= m; ++i) S.insert(read());
    for(int i = 1; i <= n; ++i) {
        it = S.upper_bound(a[i]);
        if (it != S.begin()) it --;
        s[i] = *it;
        S.erase(it);
        S.insert(hur[i]);
        ll x, y;
        ll g = exgcd(s[i], p[i], x, y);
        x = (x % p[i] + p[i]) % p[i];
        if (a[i] % g) {
            puts("-1");
            break;
        }
        p[i] /= g;
        a[i] /= g;
        a[i] = qtime(x, a[i], p[i]);
    }
}
Comments

添加新评论