洛谷P2421题解

洛谷P2421题解

九月 05, 2021

洛谷P2421
这一道题目是一道同余的题目，进行推理后用扩展欧几里得就可以了，解析我写在了代码里面

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
#include<bits/stdc++.h>
#define Int64 long long
#define maxn 17
using namespace std;
Int64 c[maxn],p[maxn],l[maxn];
//出生地，速度，生命长度 
int Extend_gcd(Int64 a,Int64 b,int &x,int &y){
	//ax+by=gcd(a,b);
	if(!b){
		x=1;y=0;
		return a;
	}
	int d=Extend_gcd(b,a%b,x,y);
	int tmp=x;
	x=y;y=tmp-a/b*y;
	return d;
}
int n;
bool check(int pos){
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n;j++){
			int x,y,t;
			t=Extend_gcd((p[i]-p[j]),pos,x,y);
			//t=gcd((p[i]-p[j]),pos)
			if((c[j]-c[i])%t)continue;
			/*
			*因为解的方程是(p[i]-p[j])x+pos*y =c[j]-c[i];
			*如果说不整除，那么就没有解 
			*/
			Int64 tmp=pos/t;
			//用pos除以t，得到每一次 x改变多少 
			tmp=abs(tmp);
			//保证tmp是正数 
			x=x%tmp*((c[j]-c[i])/t)%tmp;
			((x%=tmp)+=tmp)%=tmp;
			//对解进行修正 
			if(!x)x+=tmp;
			if(x<=min(l[j],l[i]))return false ;
		} 
	}
	return true ;
}
int main(){
	scanf("%d",&n);
	Int64 pos=0;
	for(int i=1;i<=n;i++){
		cin>>c[i]>>p[i]>>l[i];
		pos=max(pos,c[i]);//寻找最大的序号 
	}
	while(true){
		if(check(pos)){
			printf("%lld",pos);
			break;
		}
		pos++;
	} 
	return 0;
}