拓展歐幾里得 [Noi2002]Savage

對于一個野人，他（她？）所在的位置，（C[i]+x*p[i]）%ans,是的，暴力枚舉每一個ans，用拓展歐幾里得求出每兩個wildpeople(wildrage?)相遇的年份，如果小于最小的壽限（就是說他們在有生之年相遇了），那么就不符合情況。注意貌似有好多求同余的辦法，貌似沒幾個是對的。。。但我保證我的是對的。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,c[20],p[20],l[20],ans=0,a,b;
int gcd(int x,int y){return y==0? x:gcd(y,x%y);}
void ex_gcd(int a,int b,int &x,int &y)
{if(!b){x=1;y=0;return;}ex_gcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;
}
int check(int m)
{for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){a=p[i]-p[j],b=m;int d=c[j]-c[i];int k=gcd(a,b);if(d%k)continue;int x,y;a/=k;b/=k;ex_gcd(a,b,x,y);b=abs(b);x=x*d/k;x%=b;if(x<0)x+=b;if(x<=min(l[i],l[j]))return 0;}return 1;
}
int yjn()
{freopen("savage.in","r",stdin);freopen("savage.out","w",stdout);cin>>n;for(int i=1;i<=n;i++){scanf("%d%d%d",&c[i],&p[i],&l[i]);ans=max(ans,c[i]);}for(int i=ans;;i++)if(check(i)){ans=i;break;}cout<<ans;
}
int qty=yjn();
int main(){;}