1407: [Noi2002]Savage

其实答案远不到1e6

所以可以枚举！

设答案是m

那\(i,j\)的相遇就可以表示成\(P_ix+C_i=P_jx+C_j+ym\)

移向就是\((P_i-P_j)x-ym=C_j-C_i\)

套扩展欧几里得定理

如果\(C_j-C_i\mod gcd\ !=0\)说明不会相遇

否则的话求一下第一次相遇时间，如果大于一个的寿命也不会相遇

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define M 1000010

using namespace std;

int n,m,k,c[M],l[M],p[M],maxx,x,y;

int exgcd(int a,int b,int &x,int &y)

{

	if(!b) {x=1, y=0; return a;}

	int tmp=exgcd(b,a%b,y,x);

	y-=a/b*x; return tmp;

}

bool check(int k)

{

	for(int i=1;i<=n;i++)

		for(int j=i+1;j<=n;j++)

		{

			int a=p[i]-p[j], b=c[j]-c[i];

			if(a<0) a=-a, b=-b;

			int g=exgcd(a,k,x,y);

			if(b%g) continue;

			x*=b/g; int f=k/g;

			x=(x%f+f)%f; if(!x) x=f;

			if(x<=min(l[i],l[j])) return 0;

		}

	return 1;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d%d%d",&c[i],&p[i],&l[i]), m=max(m,c[i]);

	for(;;m++) if(check(m)) break;

	printf("%d",m);

}

巴特西

1407: [Noi2002]Savage

最新文章

热门文章