Bzoj1407 Savage

Description

Input

第1行为一个整数N(1<=N<=15)，即野人的数目。第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

Output

仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于106。

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

该样例对应于题目描述中的例子。

考虑两个野人i、j的情况：设他们在x年后相遇，则得到该式: P[i]*x+C[i]=P[j]*x+C[j]（mod M）

化为同余方程： (P[i]-P[j])*x+k*M=C[j]-C[i]

按照题目要求，我们需要找到一个M，使得上式无解或者x>min(C[i],C[j]) (在野人有生之年没有相遇)

问题扩展到所有野人，由于数据范围很小，可以直接枚举M，判断是否所有野人之间都满足要求。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int mxn=1000;
 8 int c[mxn],le[mxn],p[mxn];
 9 int n;
10 int m;
11 int gcd(int a,int b){
12     return b?gcd(b,a%b):a;
13 }
14 int exgcd(int a,int b,int &x,int &y){
15     if(b==0){
16         x=1;
17         y=0;
18         return a;
19     }
20     exgcd(b,a%b,x,y);
21     int t=x;
22     x=y;
23     y=t-(a/b)*y;
24 }
25 bool judge(int m){
26 
27     int i,j;
28     int t,x,y;
29     for(i=1;i<n;i++){
30         for(j=i+1;j<=n;j++){
31             int a=p[i]-p[j];
32             int b=m;
33             int c1=c[j]-c[i];
34             t=gcd(a,b);
35 
36             if(c1%t==0){
37                 a/=t;b/=t;c1/=t;
38                 exgcd(a,b,x,y);
39                 b=abs(b);
40                 x=((c1*x)%b+b)%b;
41                 if(!x)x+=b;
42                 if(x<=min(le[i],le[j]))return 0;
43             }
44         }
45     }
46     return 1;
47 }
48 int main(){
49     scanf("%d",&n);
50     int i,j;
51     m=0;
52     for(i=1;i<=n;i++){
53         scanf("%d%d%d",&c[i],&p[i],&le[i]);
54         if(c[i]>m)m=c[i];
55     }
56     for(i=m;i;i++){
57         if(judge(i)){
58             printf("%d
",i);
59             break;
60         }
61     }
62     return 0;
63 }