【BZOJ 1407】 [Noi2002]Savage

1407: [Noi2002]SavageTime Limit:5 SecMemory Limit:64 MBSubmit:793Solved:354[Submit][Status][Discuss]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

31 3 42 7 33 2 1

Sample Output

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

枚举+扩展欧几里得

（一开始以为满足二分性，实际并不满足，反例很好举）

为了取模方便，把山洞的标号都-1，使之从0开始。

枚举山洞个数为m，判断是否可行：

xi是初始山洞，ei是每年走过的山洞数，oi是野人的年龄

对于任意两个野人，计算出他们相遇需要的年数k：

xi+ei*k=xj+ej*k (mod m)

(ej-ei)*k=xi-xj (mod m)

只要该方程有解，且解<=oi,<=oj那么m就不成立。

#include <iostream>#include <algorithm>#include <cmath>#include <cstdio>#include <cstdlib>#define inf 0x3f3f3f3f#define LL long longusing namespace std;int o[20],e[20],x[20],n;int d,xx,y;void exgcd(int a,int b,int &d,int &x,int &y){if (!b){d=a,x=1,y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}int ok(int m){for (int i=1;i<n;i++)for (int j=i+1;j<=n;j++){int dx=((x[j]-x[i])%m+m)%m,de=((e[i]-e[j])%m+m)%m;exgcd(de,m,d,xx,y);if ((dx%d)!=0) continue;dx/=d;int mm=m/d;int k=(dx*xx%mm+mm)%mm;if (k<=o[i]&&k<=o[j])return 0;}return 1;}int main(){scanf("%d",&n);int ma=0;for (int i=1;i<=n;i++){scanf("%d%d%d",&x[i],&e[i],&o[i]);ma=max(x[i],ma);x[i]–;}for (int i=ma;;i++)if (ok(i)){cout<<i<<endl;return 0;}return 0;}

感悟：

1.形如ax=b (mod c)可以转化为ax+cy=b (mod c)，然后a,b,c同时mod gcd(a,c)再求

我不敢说我可以忘却，或者勇敢，坚强，等等等等一切堂皇而陈旧的字眼。