分析
假设野人i,j在某一年相遇了,则出现:$$ man[i].c+x∗man[i].p\equiv man[j].c+x∗man[j].p(\bmod m) $$
如果要让他们不相遇,则需要让这个同余方程无解,或解出的最小的x比两个人中任何一人的寿命长。
将上式变形得到:$$ x∗(man[i].p-man[j].p)-y*m = (man[j].c-man[i].c) $$
令a=man[i].p-man[j].p,b=man[j].c-man[i].c
原式变为:
$$ xa-ym=b $$
解得d如果不能被b整除,说明无解,继续向下判断(continue);
否则求出最小的x,如果x小于0,则需要+abs(m/d)求出大于0的最小值。
判断此时x和两个野人的生存时间关系,最小的x比两个人中任何一人的寿命长 不成立,直接退出.
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m;
struct node{
int c,p,l;
}man[20];
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1ll,y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
bool flag;
bool jdg(int x,int i,int j)
{
flag=true;
if (x<=min(man[i].l,man[j].l)) //最小的x比两个人中任何一人的寿命长 不成立,直接退出
{
flag=false;
return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>man[i].c>>man[i].p>>man[i].l;
m=max(m,man[i].c);
}
if(n==1) //只有一个野人,则只需要一个洞
{
puts("1");
return 0;
}
while(1)
{
flag=true;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
LL x,y,a,b;
a=man[i].p-man[j].p;
b=man[j].c-man[i].c;
LL d=exgcd(a,m,x,y);
if(b%d) continue; //无解,继续判断
x*=b/d;
x=x%(m/d);
if(x<0) x+=abs(m/d);
if(!jdg(x,i,j)) break;
}
if(!flag) break;
}
if(flag) //所有野人的关系均成立,则输出这个m
{
cout<<m<<endl;
return 0;
}
m++; //m++进入下一次大循环
}
return 0;
}
%%%
Orz tnmql
Orz tnmql