「SOL」屠龙勇士(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」屠龙勇士(LOJ)

发表于 分类于 Valine：

写题解当作复习笔记
（这样就可以少写一篇博客了 Yeah）

# 题面

> Link LOJ 2721

# exCRT

「问题」

求解线性同余方程组

$$ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \cdots\\ x\equiv a_n\pmod{m_n} \end{cases} $$

$m$ 可以不互质。

考虑等价地合并两个同余方程：

可以把同余方程写为不定方程的形式，于是得到参数的一些关系：

由于 $m_1,m_2$ 不一定互质，所以关于 $k_1,k_2$ 的不定方程不一定有解。具体地说，设 $(m_1,m_2)=g$，则

等式左侧 $g\mid k_1m_1-k_2m_2$，则右侧也必须满足 $g\mid a_2-a_1$，否则无解。

若满足上述条件，则等式两边同时除以 $g$ 仍然等价，即

此时 $(m_1’,m_2’)=1$，可以直接用 exGCD 解决上述问题，得到 $k_1$ 的一个特解为 $k_0$。由

可以知道 $k_1$ 的通解为 $k_1=k_0+nm_2’(n\in\mathbb{Z})$。

将 $k_1$ 代回 $x$ 的表达式，则有

于是就得到了两个式子合并后的等价的式子。这样不断合并就可以得到最终 $x$ 的通解。

# 解析

一开始可以根据输入求出「用哪一把剑攻击第 $i$ 条龙」，记为 $w_i$。具体可以用 multiset 实现。

点击展开/折叠multiset使用技巧

multiset 内部每个位置储存了一个元素（并不是把相同的元素合到同一个位置并且记录次数），因此用迭代器 iterator 访问其中的某个位置，访问到的是单个元素。如果按迭代器顺序访问 multiset，就相当于把插入的所有元素排了个序。

multiset 内置有 lower_bound 和 upper_bound 函数，前者返回第一个大于等于给定值的元素的迭代器，后者返回第一个严格大于给定值的元素的迭代器。

multiset 的 delete 函数有两类参数。第一类是给定数值，会删除其中所有该数值；第二类是给定迭代器，会删除迭代器对应的元素——这样就只会删掉一个数字。

利用这些特点，我们可以用 upper_bound 找到第一把攻击力大于龙的生命值的剑，而上一把剑就是攻击力小于等于生命值的剑。然后用 delete 删除该剑的迭代器（不能是数值！）。

记龙的生命为 $h_i$，回复力为 $r_i$，则有两个限制：

  • 攻击后龙的生命模 $r_i$ 余 $0$；
  • 攻击后，龙的生命小于等于 $0$。

问题直接转化为 $n$ 对方程构成的方程组

不等式方程可以求出 $x$ 的下界。考虑如何求解同余方程。

$w_i,r_i$ 不一定互质，于是可能本身就无解。记 $(w_i,r_i)=g_i$，则必须满足 $g_i\mid h_i$，方程才有解。

满足有解的条件后，$w_i,h_i,r_i$ 同时除以 $g_i$，得到等价的方程 $w_i’x=h_i’\pmod {r_i’}$，此时 $(w_i’,r_i’)=1$，$w_i’$ 存在逆元，于是可以得到

这个方程就可以用 exCRT 了。

# 源代码

点击展开/折叠代码 
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
117
118
119
/*Lucky_Glass*/
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

template<class T>T rin(T &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
typedef long long llong;
const int N=1e5+10;
#define con(type) const type &

multiset<llong> sword;
int n,m;
llong ih[N],rec[N],rew[N],atk[N];

llong ina_GCD(con(llong)a,con(llong)b){return b?ina_GCD(b,a%b):a;}
llong ex_GCD(con(llong)a,con(llong)b,llong &x,llong &y){
	if(!b){x=1,y=0;return a;}
	llong ret=ex_GCD(b,a%b,x,y);
	swap(x,y);
	y-=a/b*x;
	return ret;
}
llong ina_ABS(con(llong)a){return a<0?-a:a;}
llong mul(llong a,llong b,llong mod){
	bool neg=(a<0)^(b<0);
	a=ina_ABS(a),b=ina_ABS(b);
	a%=mod,b%=mod;
	llong ret=0;
	while(b){
		if(b&1) ret=(ret+a)>=mod? ret+a-mod:ret+a;
		a<<=1,b>>=1;
		if(a>=mod) a-=mod;
	}
	if(neg && ret) return mod-ret;
	return ret;
}
pair<llong,llong> comb_CRT(con(llong)m0,con(llong)r0,con(llong)m1,con(llong)r1){
	llong g=ina_GCD(m0,m1);
	if((r1-r0)%g){
		// printf("(%lld,%lld)=%lld %lld %lld\n",m0,m1,g,r1,r0);
		return make_pair(-1ll,-1ll);
	}
	llong p,q;
	ex_GCD(m0/g,m1/g,p,q);
	p=mul((r1-r0)/g,p,m1/g);
	llong m2=m0/g*m1,r2=(mul(p,m0,m2)+r0)%m2;
	if(r2<0) r2+=m2;
	return make_pair(m2,r2);
}
llong solve(){
	sword.clear();
	rin(n),rin(m);
	for(int i=1;i<=n;i++) rin(ih[i]);
	for(int i=1;i<=n;i++) rin(rec[i]);
	for(int i=1;i<=n;i++) rin(rew[i]);
	for(int i=1,tmp;i<=m;i++) sword.insert(rin(tmp));
	for(int i=1;i<=n;i++){
		multiset<llong>::iterator it=sword.upper_bound(ih[i]);
		if(it!=sword.begin()) it--;
		atk[i]=*it;
		sword.erase(it);
		sword.insert(rew[i]);
	}
	llong mnbon=0;
	pair<llong,llong> now(-1ll,-1ll);
	for(int i=1;i<=n;i++){
		mnbon=max(mnbon,(ih[i]+atk[i]-1)/atk[i]);
		llong k=atk[i],r=ih[i],m=rec[i];
		// printf("%lld x = %lld (mod %lld) -> ",k,r,m);
		//kx = r (mod m)
		k%=m,r%=m;
		if(!k){
			if(r){
				// printf("A\n");
				return -1ll;
			}
			continue;
		}
		llong g=ina_GCD(k,m);
		if(r%g){
			// printf("B\n");
			return -1ll;
		}
		k/=g,m/=g,r/=g;
		llong invk,non;
		ex_GCD(k,m,invk,non);
		invk=(invk%m+m)%m;
		r=mul(r,invk,m);
		// printf("x = %lld (mod %lld)\n",r,m);
		pair<llong,llong> tmp(m,r);
		if(i==1) now=tmp;
		else now=comb_CRT(now.first,now.second,tmp.first,tmp.second);
		if(now.first==-1){
			// printf("C\n");
			return -1ll;
		}
	}
	if(now.first==-1) return mnbon;
	if(now.second>=mnbon) return now.second;
	else{
		llong k=(mnbon-now.second+now.first-1)/now.first;
		return now.second+k*now.first;
	}
}
int main(){
	// freopen("input.in","r",stdin);
	freopen("dragon.in","r",stdin);
	freopen("dragon.out","w",stdout);
	int cas;rin(cas);
	while(cas--) printf("%lld\n",solve());
	return 0;
}

THE END

Thanks for reading!

祈愿在风中渐渐冷冽
那一刻她眼底有华光泯灭
海潮呼啸着哽咽
想把不舍宣泄
所有分别都太决绝
回忆都太炽烈
最后一面何处去借

——《流光幻夜》By 司夏

\> Link [流光幻夜](http://music.163.com/song?id=1817417571&userid=303853271)-网易云