题目描述
克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。
每个野人i有一个寿命值Li，即生存的年数。
下面四幅图描述了一个有6个山洞，住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1，2，3；每年要走过的洞穴数依次为3，7，2；寿命值依次为4，3，1。
奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？
输入输出格式
输入格式：
第1行为一个整数N(1<=N<=15)，即野人的数目。
第2行到第N+1每行为三个整数Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。
输出格式：
仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。
思路：
既然要求每两个野人永远不能碰面的最少山洞数，我们不妨先看一下数据范围
已知洞穴数小于1e6，那么我们就可以枚举洞穴数量，然后判定是否成立
怎么判定呢？
我们现在已经枚举出了洞穴的数量，然后我们就知道了模数的大小，
就可以利用exgcd两两验证
比如说验证i与j两个位置
则两个野人相遇时，应满足：
yearly[i]*x+start[i]≡start[j]+yearly[j]*x （mod p）
转化一下就是exgcd的形式
验证即可
代码：
#include<iostream> #include<cstdio> #include<cmath> #define rii register int i #define rij register int j using namespace std; int yearly[20],start[20],life[20],x,y,n,ans,maxn; int gcd(int a,int b) { if(b!=0) { return gcd(b,a%b); } else { return a; } } void exgcd(int ltt,int lzn) { if (lzn!=0) { exgcd(lzn,ltt%lzn); int kkk=x; x=y; y=kkk-ltt/lzn*y; } else { x=1; y=0; } } int check() { for(rii=1;i<=n-1;i++) { for(rij=i+1;j<=n;j++) { int kkk=start[i]-start[j]; int ltt=ans; int lzn=yearly[j]-yearly[i]; int qwq=gcd(kkk,ltt); if(lzn%qwq!=0) { continue; } exgcd(kkk,ltt); ltt=abs(ltt/qwq); x=(x/qwq*lzn%ltt+ltt)%ltt; if(x==0) { x+=ltt; } if(x<=min(life[i],life[j])) { return 1; } } } return 0; } int main() { scanf("%d",&n); for(rii=1;i<=n;i++) { scanf("%d%d%d",&yearly[i],&start[i],&life[i]); maxn=max(yearly[i],maxn); } ans=maxn; while(check()!=0) { ans++; } printf("%d",ans); }