题目大意

给出$n$只野人，第$i$只野人一开始会住在山洞$pos_i$里，每年会顺时针往前走$step_i$个山洞住下来，寿命是$age_i$

假设山洞是环形排布，且野人在有生之年都不会见到他的同类，询问山洞的最少个数

数据范围

$1\leqslant n\leqslant 15，1\leqslant pos_i,step_i<=100, 0\leqslant age_i\leqslant 106$

数据保证有解，且不超过106

题解

拓展欧几里得，学习感谢大神系列

P.S.大神的代码是贴错了吧，不用看代码，看题解即可

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
       int x=0,f=1;char ch=getchar();
       while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
       while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
       return x*f;
}

int n,mx;
int pos[20],step[20],age[20];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void exgcd(int a,int b,int &x,int &y){ 
    if (b==0){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y; 
}

inline int judge(int m){
    int a,b,c,g,x,y;
    For(i,1,n-1) For(j,i+1,n){
        a=step[i]-step[j],b=m,c=pos[j]-pos[i];
        g=gcd(a,b);
        if (c%g==0){
            a/=g,b/=g,c/=g;
            exgcd(a,b,x,y);
            b=abs(b);
            x=((c*x)%b+b)%b;
            if (!x) x+=b;
            if (x<=min(age[i],age[j])) return 0; 
        }
    }
    return 1;
} 

int main(){
    n=read();
    For(i,1,n){
        pos[i]=read(),step[i]=read(),age[i]=read();
        mx=max(pos[i],mx);
    }
    For(i,mx,inf)
        if (judge(i)) {printf("%d\n",i);return 0;} 
    return 0;
}