题目描述

样例

3
1 3 4
2 7 3
3 2 1

6

分析

首先，我们先设4个变量，初始坐标d[i]，每年步数p[i]，寿命l[i]，根据题目很容易得到一个不等式

(假设i，j是两个野人的标号，x为经过的年数)：(d[i] + p[i] * x) % m != (d[j] + p[j] * x) % m 。

解不等式。。。不会，但可以转化一下，把不等式转为等式(d[i] + p[i] * x) % m = (d[j] + p[j] * x) % m，使等式无解，

无解条件就是解得的x的最小，正整数解比两个野人的其中一个的寿命要大即可。

但这个等式用代码解就需要转换一下，假设(d[i] + p[i] * x) % m = (d[j] + p[j] * x) % m = t，

(d[i] + p[i] * x) = m * y1+t，(d[j] + p[j] * x) = m * y2+t。

那么等式就可以化为：d[i] + p[i] * x - m * y1 = d[j] + p[j] * x - m * y2;

即为： d[i] - d[j] = (p[i] - p[j]) * x + m * (y1 - y2)。这就转化成了 ax+by=c 的形式，

可以用扩展欧几里得定理做，这里的y对答案无贡献，可忽略， 接下来就是用公式求最小正整数解了。

补如何求ax + by = c的最小正整数解

对于 ax + by = c的方程， 先用扩展欧几里得解出方程 ax + by = gcd(a,b)的一组解 (x,y)，

接着判断 c % gcd(a,b) 是否等于0，如果不等于则方程无解

然后假设b1 = b / gcd(a,b)，x1 = (x + b1) * （c / gcd(a,b) ）;

那么方程的最小正整数解为x1 = (x1 % b1 + b1) % b1,y1 = (c - a * x1) / b;

solution

#include<bits/stdc++.h>
const int maxn=1<<5;
const int inf=0x7f7f7f7f;
using namespace std;
int n,r,m,q,x,y,a,b,t,d[maxn],p[maxn],l[maxn];

int exgcd(int a,int b,int &x,int &y) {	//解方程模板 
    if (b==0) {
        x=1;
        y=0;
        return a;
    }
    int ret=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return ret;
}

bool check(int z)
{
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)		//枚举没两个野人，看是否符合方程 
		{
			a=p[i]-p[j];
			b=d[j]-d[i];
			m=z;
			x=0,y=0;
			int q=exgcd(a,m,x,y);	//gcd(a,b) 
			if(b%q)continue;		//无解 
			b/=q;					// b此时等价于c/gcd(a,b); 
			m/=q;					//等价于上面的b1
			if(m<0)m=-m;			//不确定正负 
			t=(x+m)*b;
			t=(t%m+m)%m;			//最小正整数解公式 
			if(t<=l[i]&&t<=l[j]) return 0;		//方程无解 
		}
	}
	return 1;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&d[i],&p[i],&l[i]),r=max(r,d[i]);
	for(int i=r;i<=1e6;i++)			//枚举到极限数据，找到最小的就输出 
	{
		if(check(i))
		{
			printf("%d\n",i);
			return 0;
		}
	}
	
	return 0;
}