UVA, 10413 Crazy Savages

题意：给你几个野人，他们住在一个山的环形洞里他们的初始位置下一次走几步几天后消失求有几个洞他们不会打起来

效果如图：

思路：扩展欧几里得

参考代码：http://blog.csdn.net/pi9nc/article/details/12223357

= =扩展欧几里得我学得真鶸，后面好好弄一下

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 const int N=100;
 9 int c[N],p[N],l[N];
10 int ans;
11 
12 int extend_gcd(int a,int b,int &x,int &y)
13 {
14     if(b==0)
15     {
16         x=1;y=0;
17         return a;
18     }
19     else
20     {
21         int r=extend_gcd(b,a%b,y,x);
22         y-=x*(a/b);
23         return r;
24     }
25 }
26 
27 void datecle()
28 {
29     memset(c,0,sizeof(c));
30     memset(p,0,sizeof(p));
31     memset(l,0,sizeof(l));
32 }
33 
34 void datecin(int n)
35 {
36     datecle();
37     ans=0;
38     for(int i=0;i<n;i++)
39     {
40         scanf("%d%d%d",&c[i],&p[i],&l[i]);
41         ans=max(ans,c[i]);//从最大值算起
42     }
43 }
44 
45 bool datecal(int m,int n)//解方程P*x+m*y=C
46 {
47     for(int i=0;i<n;i++)
48     {
49         for(int j=i+1;j<n;j++)
50         {
51             int x,y;
52             int C=c[i]-c[j];
53             int P=p[j]-p[i];
54             int d=extend_gcd(P,m,x,y);
55             if(C%d)//判断是否有解
56                 continue;
57             x*=C/d;
58             if(d<0) d=-d;
59             x=(x%(m/d)+m/d)%(m/d);//取x最小值
60             if(x<=l[i]&&x<=l[j])
61                 return false;
62         }
63     }
64     return true;
65 }
66 
67 int main()
68 {
69     int t,n;
70     scanf("%d",&t);
71     while(t--)
72     {
73         scanf("%d",&n);
74         datecin(n);
75         while(1)
76         {
77             if(datecal(ans,n))
78                 break;
79             ans++;
80         }
81         printf("%d
",ans);
82     }
83     return 0;
84 }