BZOJ1407:[NOI2002]Savage(exgcd)

Description

Input

第1行为一个整数N(1<=N<=15)，即野人的数目。

第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

(1<=Ci,Pi<=100, 0<=Li<=10^6 )

Output

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

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

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

Solution

这不是我qbxt的时候秒了正解结果以为复杂度不对没敢讲的题么
我们发现m的最大值很小，所以我们可以枚举m，然后n个野人两两判断
怎么判断呢？$c[i]+x*p[i] equiv c[j]+x*p[j];(mod;m)$

exgcd求解即可。
如果解小于max(l[i],l[j])，那么这两个野人有生之年可以相遇

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (1000000+1000)
 5 using namespace std;
 6 
 7 int c[N],p[N],l[N],maxnum,n,x,y;
 8 
 9 int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
10 void exgcd(int a,int b,int &x,int &y)
11 {
12     if (!b){x=1; y=0; return;}
13     exgcd(b,a%b,y,x); y-=x*(a/b);
14 }
15 
16 bool check(int m)
17 {
18     for (int i=1; i<=n-1; ++i)
19         for (int j=i+1; j<=n; ++j)
20         {
21             int A=p[i]-p[j], B=m, C=c[j]-c[i];
22             int g=gcd(A,B);
23             
24             if (C%g) continue;
25             A/=g; B/=g; C/=g;//不保证A,B互质 
26             exgcd(A,B,x,y);
27             
28             if (B<0) B=-B;
29             x*=C; x=(x%B+B)%B;
30             if (x<=min(l[i],l[j])) return false;
31         }
32     return true;
33 }
34 
35 int main()
36 {
37     scanf("%d",&n);
38     for (int i=1; i<=n; ++i)
39     {
40         scanf("%d%d%d",&c[i],&p[i],&l[i]);
41         maxnum=max(maxnum,c[i]);
42         c[i]--;
43     }
44     for (int i=maxnum; i<=1000000; ++i)
45         if (check(i))
46         {
47             printf("%d",i);
48             return 0;
49         }
50 }