[NOI2018]屠龙勇士

第一行一个整数 T ，代表数据组数。
接下来 T 组数据，每组数据包含 5 行。
• 每组数据的第一行包含两个整数，n 和 m ，代表巨龙的数量和初始剑的数量;
• 接下来一行包含 n 个正整数，第 i 个数表示第 i 条巨龙的初始生命值 ai;
• 接下来一行包含 n 个正整数，第 i 个数表示第 i 条巨龙的恢复能力 pi
• 接下来一行包含 n 个正整数，第 i 个数表示杀死第 i 条巨龙后奖励的剑的攻击力;
• 接下来一行包含 m 个正整数，表示初始拥有的 m 把剑的攻击力。

C++14(g++5.4) 解法, 执行用时: 1380ms, 内存消耗: 9948K, 提交时间: 2019-05-30 19:34:54

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100000+10;
int n,m,flag;ll a[maxn],p[maxn],b[maxn],c[maxn],A[maxn],B[maxn],Max;
multiset<ll> s;
multiset<ll>::iterator it;

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

inline ll mul(ll a,ll b,ll mod){
    ll ret=0;b=(b%mod+mod)%mod;
    for(;b;b>>=1,a=(a+a)%mod)
        if(b&1) ret=(ret+a)%mod;
    return ret;
}

inline void merge(ll &a1,ll &b1,ll a2,ll b2){
    ll d=a2-a1,g,x,y;
    exgcd(b1,b2,g,x,y);
    if(d%g==0){
        x=(mul(x,d/g,b2/g)+(b2/g))%(b2/g);
        a1=x*b1+a1;b1=b1/g*b2;
    }
    else flag=1;
}

inline ll excrt(ll *a,ll *b){
    ll a1,b1,a2,b2;
    a1=a[1];b1=b[1];
    for(int i=2;i<=n;i++){
        a2=a[i];b2=b[i];
        merge(a1,b1,a2,b2);
        if(flag) return -1;
    }
    if(a1>=Max) return a1;
    return a1+((Max-a1)/b1+((Max-a1)%b1?1:0))*b1;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);flag=Max=0;s.clear();
        ll d,g,x,y;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
        for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
        for(int i=1;i<=m;i++){
            scanf("%lld",&x);
            s.insert(x);
        }
        for(int i=1;i<=n;i++){
            it=s.upper_bound(a[i]);
            if(it!=s.begin()) it--;
            c[i]=*it;s.erase(s.find(*it));s.insert(b[i]);
            Max=max(Max,a[i]/c[i]+(a[i]%c[i]?1:0));
        }

        for(int i=1;i<=n;i++){
            d=a[i];exgcd(c[i],p[i],g,x,y);
            if(d%g){flag=1;break;}
            x=(mul(x,d/g,p[i]/g)+(p[i]/g))%(p[i]/g);
            A[i]=x;B[i]=p[i]/g;
        }
        if(flag) printf("-1\n");
        else printf("%lld\n",excrt(A,B));
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 606ms, 内存消耗: 8284K, 提交时间: 2023-07-16 16:11:10

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

const int N=1e5+10;
long long r[N];
long long m[N];
long long q[N];
long long at[N];
int n,k;
long long gcd(long long a,long long b)
{
	return b?gcd(b,a%b):a;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long x1,y1,d;
	d=exgcd(b,a%b,x1,y1);
	x=y1;
	y=x1-a/b*y1;
	return d;
}
long long lcm(long long a,long long b)
{
	return a/gcd(a,b)*b;
}
int tp;
long long mx=0;
long long CRT()
{
	tp=n;
	long long ans=0,M=1,A,B,C,x,y;
	for(int i=1;i<=tp;i++)
	{
		A=(__int128)at[i]*M%m[i];
		B=m[i];
		C=(r[i]-at[i]*ans%m[i]+m[i])%m[i];
		long long d=exgcd(A,B,x,y);
		if(C%d) return -1;
		x=(x%B+B)%B;
		ans+=(__int128)(C/d)*x%(B/d)*M%(M*=B/d);
		ans%=M;
	}
	if(ans<mx) ans=((mx-1)/M+1)*M;
	return ans;
}
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>r[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>m[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>q[i];
	}
	multiset<long long>s;
	for(int i=1;i<=k;i++)
	{
		long long x;
		cin>>x;
		s.insert(x);
	}
	mx=0;
	for(int i=1;i<=n;i++)
	{
		multiset<long long>::iterator it=s.upper_bound(r[i]);
		if(it!=s.begin()) it--;
		at[i]=*it;
		s.erase(it);
		s.insert(q[i]);
		mx=max(mx,(r[i]-1)/at[i]+1);
	}
	cout<<CRT()<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

详情