克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人，一开始依次住在山洞C1,C2,…,CN中，以后每年，第i个野人会沿顺时针向前走Pi个洞住下来。
每个野人i有一个寿命值Li，即生存的年数。
奇怪的是，虽然野人有很多，但没有任何两个野人在有生之年处在同一个山洞中，使得小岛一直保持和平与宁静，这让科学家们很是惊奇。他们想知道，至少有多少个山洞，才能维持岛上的和平呢？
根据题目，设(x)为相遇天数，可以得到式子
[c_{i}+p_{i} imes xequiv c_{j}+p_{j} imes x(mod M) (1le i,jle N)
]
我们要保证对于每一对((i,j))，这个式子都要无解或者求出来的(x>min(l[i],[j]))，即在两个人有一个人死了之后相遇
把这个式子化一下，就变成了
[(p_i-p_j) imes xequiv c_j-c_i(mod M)
]
写成方程的形式
[(p_i-p_j) imes x+M imes y=c_j-c_i
]
怎么解呢，我们不妨设(a=p_i-p_j,b=M,c=c_i-c_j)
方程就成了
[ax+by=c
]
设(g=gcd(a,b))，当(g|c)时，设(a'=a/g,b'=b/g,c'=c/g)
我们可以用(exgcd)，即扩展欧几里得算发求出(a'x'+b'y'=1)的一组解(x',y')
两边乘(c')，得到(a'c'x'+b'c'y'=c')
两边乘(g)，得到(a'gc'x'+b'gc'y'=c'g)
化简得到(ac'x'+bc'y'=c)
于是我们得到了方程一组解(x_0=x'c',y_0=y'c')
因为(M)最大到(10^6)，所以从(Max_{i=1}^{n}c_i-10^6)枚举(M)，如果方程都无解或者(x>min(l[i],[j]))，那这个(M)就是答案了
Code
#include <iostream>
#include <cstdio>
#define N 1000000
#define int long long
using namespace std;
int n,d[500],p[500],l[500],mm;
int gcd(int x,int y)
{
if (!y)return x;
return gcd(y,x%y);
}
void exgcd(int a,int b,int &x,int &y)
{
if (!b)x=1,y=0;
else
{
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
int check(int m)
{
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
{
int a=p[i]-p[j],b=m,c=d[j]-d[i],g=gcd(a,b),x,y;
if (c%g!=0)continue;
a/=g,b/=g,c/=g;
exgcd(a,b,x,y);
if (b<0)b=-b;
x=(x*c%b+b)%b;
if (x<=min(l[i],l[j]))return 0;
}
return 1;
}
signed main()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>d[i]>>p[i]>>l[i],mm=max(mm,d[i]);
for (int i=mm;i<=N;i++)
{
if (check(i))
{
cout<<i<<endl;
return 0;
}
}
return 0;
}