题目描述
样例
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;
}
标签:Savage,正整数,gcd,荒岛,野人,b1,y1,ax,x1
From: https://www.cnblogs.com/oceansofstars/p/18101890