BZOJ1407: [Noi2002]Savage

BZOJ1407: [Noi2002]Savage

---

题目描述

传送门

题目分析

看看题目让我们求什么。

就是给出了(n)组(C,P,L)，求一个最小的(M)。

(M)满足对于任意两组(C,P,L)，使

[C_i+P_i imes xequiv C_j+P_j imes x (mod M) ]

其中解出的(x)要满足(x<min(L_i,L_j))或者根本就无解。

对上面那个式子可以移项

[P_i imes x-P_j imes xequiv C_j-C_i(mod M) ]

然后设(a=(P_i-P_j),b=(C_i-C_j))

可以明显发现刚才那个式子是一个同余方程，使用exgcd求解即可。

是代码呢

#include <bits/stdc++.h>
using namespace std;
int n,m,mx,p[150],l[150],d[150];
inline int exgcd(int a,int b,int &x,int &y)
{
	if(!b) {x=1,y=0;return a;}
	int g=exgcd(b,a%b,x,y);
	int t=x;x=y;y=t-(a/b)*y;
	return g;
}
inline bool check(int m)
{
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++){
			int a=p[j]-p[i],b=m,c=d[i]-d[j];
			int x=0,y=0;
			int g=exgcd(a,b,x,y);
			x=0,y=0;
			if(c%g==0){
				a/=g;b/=g;c/=g;
				exgcd(a,b,x,y);
				if(b<0) b=-b;
				x=((x*c)%b+b)%b;
				if(x==0) x+=b;
				if(x<=min(l[i],l[j])) return 0;
			}
		}
	return 1;
}
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i]>>p[i]>>l[i];
		mx=max(mx,d[i]);
	}
	while(1){
		if(check(mx)){
			printf("%d
", mx);
			return 0;
		}
		mx++;
	}
}