题目描述
克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。每个野人i有一个寿命值Li，即生存的年数。下面四幅图描述了一个有6个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1，2，3；每年要走过的洞穴数依次为3，7，2；寿命值依次为4，3，1。
奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？
Solution
我们会发现，这题和青蛙的约会有一点相像，很显然是exgcd的应用题。
首先我们读完题目可以列出一个等式：
显然我们只要让这个等式无解，就能满足野人永远追不上，而且野人是有寿命的，就是不需要永远无解。
在中间计算初始编号的差值时有可能出现负数，我们需要加一个绝对值，不然会超时（很难受）
代码：
//By Bibi
/// .-~~~~~~~~~-._ _.-~~~~~~~~~-.
/// __.' ~. .~ `.__
/// .'// \./ \\`.
/// .'// | \\`.
/// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`.
/// .'//.-" `-. | .-' "-.\\`.
/// .'//______.============-.. \ | / ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int MAXN=17;
int read(){
int sum=0,flag=1;
char c;
for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
return sum*flag;
}
int n;
int c[MAXN],p[MAXN],l[MAXN];
int maxx;
int gcd(int a,int b){
return b? gcd(b,a%b):a;
}
int exgcd(int a,int b,int &x,int &y){
if(!b) {x=1;y=0;return a;}
else {
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
}
void init(){
n=read();
rep(i,1,n) c[i]=read(),p[i]=read(),l[i]=read(),maxx=max(maxx,c[i]);
}
bool work(int m){
int a,b,C,t,x,y;
rep(i,1,n){
rep(j,i+1,n){
a=p[i]-p[j];
C=c[j]-c[i];
b=m;
t=gcd(a,b);
if(C%t==0){
a/=t,b/=t,C/=t;
exgcd(a,b,x,y);
b=abs(b);
x=((C*x)%b+b)%b;
if(!x) x+=b;
if(x<=min(l[i],l[j])) return 0;
}
}
}
return 1;
}
int main(){
init();
for(int i=maxx;;++i){
if(work(i)) {printf("%d",i);return 0;}
}
return 0;
}