Problem

http://uoj.ac/problem/396

Solution

每条恶龙使用的剑是固定的，用 multiset 模拟就行。

然后有同余方程组：
$$xATK \equiv HP \pmod {p_i}$$

求出通解之后用 EXCRT 处理就行。

注意 $hp_i=p_i$ 的情况，这样可能会使得 $ans=0$。一种方便的处理方式就是出现这种情况直接让 $ans=M$... 这样就能过 UOJ 的 Hack 了。如果我假了欢迎来打脸 orz

如果 $p_i=1$ 的话就直接特判就行了。

注意全程 int128（雾）

一开始我错了，以为是我左边带参的 EXCRT 假了，于是先将其转化为左边不带参的 EXCRT 处理。

然后发现是没改__int128。之后把原来那份代码交上去就对了？？

之前认为左边带参的 EXCRT 是通解错误的原因。但事实上再思考一下，两种方法求得的通解是等价的，因此带参 EXCRT 是可行的。

两份代码会一起放上。

Code

// Code by ajcxsu
// Problem: dragon

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
#define CLR(x) memset(x, 0, sizeof(x))
typedef long long ll;
typedef __int128 i128;
const int N=1e5+10;
i128 hp[N], p[N], atk[N];
i128 ar[N];
multiset<ll> s;

void ini() {
    s.clear();
}

i128 exgcd(i128 a, i128 b, i128 &x, i128 &y) {
    if(b==0) return x=1, y=0, a;
    assert(a>=0 && b>0);
    i128 x2, y2, g=exgcd(b, a%b, x2, y2);
    return x=y2, y=x2-a/b*y2, g;
}

int main() {
    int T, n, m;
    gn(T);
    ll na;
    while(T--) {
        gn(n), gn(m);
        ini();
        char spec=1;
        for(int i=1;i<=n;i++) gn(hp[i]);
        for(int i=1;i<=n;i++) gn(p[i]), spec&=(p[i]==1);
        for(int i=1;i<=n;i++) gn(ar[i]);
        for(int i=1;i<=m;i++) gn(na), s.insert(na);
        multiset<ll>::iterator it;
        ll mans=0;
        for(int i=1;i<=n;i++) {
            it=s.upper_bound(hp[i]);
            if(it!=s.begin()) it--;
            atk[i]=*it, s.erase(it), s.insert(ar[i]);
            mans=max(mans, ll((hp[i]-1)/atk[i]+1));
        }
        if(spec) { printf("%lld\n", mans); continue; }
        char nosol=0;
        i128 M, ans, x, y, c, g;
        M=1, ans=0;
        for(int i=1;i<=n;i++) {
            if(hp[i]==0) continue;
            c=hp[i];
            g=exgcd(atk[i], p[i], x, y);
            if(c%g!=0) { nosol=1; break; }
            c=x*(c/g)%(p[i]/g)-ans, p[i]/=g, (c+=p[i])%=p[i];
            g=exgcd(M, p[i], x, y);
            if(c%g!=0) { nosol=1; break; }
            x=x*(c/g)%(p[i]/g), ans+=x*M, M*=p[i]/g, ans=(ans%M+M)%M, ans=ans?ans:M;
        }
        printf("%lld\n",nosol?-1ll:(ll)ans);
    }
    return 0;
}

Code 2

效率更高。

// Code by ajcxsu
// Problem: dragon

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
#define CLR(x) memset(x, 0, sizeof(x))
typedef long long ll;
typedef __int128 i128;
const int N=1e5+10;
i128 hp[N], p[N], atk[N];
i128 ar[N];
multiset<ll> s;

i128 exgcd(i128 a, i128 b, i128 &x, i128 &y) {
    if(b==0) return x=1, y=0, a;
    i128 x2, y2, g=exgcd(b, a%b, x2, y2);
    return x=y2, y=x2-a/b*y2, g;
}

int main() {
    int T, n, m;
    gn(T);
    ll na;
    while(T--) {
        gn(n), gn(m), s.clear();
        char spec=1;
        for(int i=1;i<=n;i++) gn(hp[i]);
        for(int i=1;i<=n;i++) gn(p[i]), spec&=(p[i]==1);
        for(int i=1;i<=n;i++) gn(ar[i]);
        for(int i=1;i<=m;i++) gn(na), s.insert(na);
        multiset<ll>::iterator it;
        ll mans=0;
        for(int i=1;i<=n;i++) {
            it=s.upper_bound(hp[i]);
            if(it!=s.begin()) it--;
            atk[i]=*it, s.erase(it), s.insert(ar[i]);
            if(spec) mans=max(mans, ll((hp[i]-1)/atk[i]+1));
        }
        if(spec) { printf("%lld\n", mans); continue; }
        char nosol=0;
        i128 M, ans, x, y, c, g;
        M=1, ans=0;
        for(int i=1;i<=n;i++) {
            c=(hp[i]%p[i]-ans*atk[i]%p[i]+p[i])%p[i];
            g=exgcd(M*atk[i], p[i], x, y);
            if(c%g!=0) { nosol=1; break; }
            x=(x*c/g)%(p[i]/g), ans+=(!x?p[i]/g:x)*M, M*=p[i]/g, ans=(ans%M+M)%M, ans=ans?ans:M;
        }
        printf("%lld\n",nosol?-1ll:(ll)ans);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uoj-396.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆