填坑……链接：http://cogs.pro/cogs/problem/problem.php?pid=333
题意：给出环上一堆移动的点，问环至少要有多长所有点才能都不被追上。
很久之前打的这道题……然而当时并不知道原理……今天重打时才意识到原理，于是来口胡一发……
我们可以将野人之间追到看做$C[i]+x*P[i]=C[j]+x*P[j](mod m)$的一组正整数解中的$x$。如果追到，这个方程一定就是在这些野人有生之年内有整数解的。上面这个东西显然可以扩欧来解决，于是我们就可以直接枚举每一个可能的洞穴数目，答案就是让这些方程全部无合法解的最小洞穴数目。
1 #include<iostream>cogs333
2 #include<cstdio>
3 #include<algorithm>
4 #include<cstring>
5 using namespace std;
6 const int maxn=20;
7 int C[maxn],P[maxn],L[maxn],n,m;
8 int gcd(int a,int b)
9 {
10 return (!b)?a:gcd(b,a%b);
11 }
12 int exgcd(int a,int b,int &x,int &y)
13 {
14 if(!b)
15 {
16 x=1,y=0;
17 return a;
18 }
19 int d=exgcd(b,a%b,y,x);y-=x*(a/b);
20 return d;
21 }
22 int haha()
23 {
24 freopen("savage.in","r",stdin);
25 freopen("savage.out","w",stdout);
26 scanf("%d",&n);
27 for(int i=1;i<=n;i++)
28 {
29 scanf("%d%d%d",&C[i],&P[i],&L[i]);
30 m=max(m,C[i]);
31 }
32 for(int i=m;;i++)
33 {
34 bool notok=0;
35 for(int j=1;j<=n;j++)
36 {
37 for(int k=j+1;k<=n;k++)
38 {
39 int b=i,a=P[j]-P[k],c=C[k]-C[j];
40 int g=gcd(a,b);
41 if(c%g)continue;
42 a/=g,b/=g;
43 int x,y;exgcd(a,b,x,y);x=x*c/g;x%=abs(b);
44 if(x<0)x+=abs(b);
45 if(x<=L[k]&&x<=L[j])
46 {
47 notok=1;
48 break;
49 }
50 }
51 if(notok)break;
52 }
53 if(!notok)
54 {
55 printf("%d\n",i);
56 return 0;
57 }
58 }
59 }
60 int sb=haha();
61 int main(){;}