同余方程 扩展欧几里得

同余方程 扩展欧几里得。
题意就是有一些人每年按顺时针转若干个洞，求至少有多少个洞，才能使这些人在他们的有生之年会不会有两个人在同一个洞住。
转圈可以转化为同余问题，模数就是洞的数量。
根据题意，我们列出：
ci+k∗pi=cj+k∗pj(mod m)" role="presentation">ci+k?pi=cj+k?pj(modm)$$c_i+k?p_i=c_j+k?p_j(modm)$$
然后移项
k∗(pi−pj)=cj−ci(mod m)" role="presentation">k?(pi?pj)=cj?ci(modm)$$k?(p_i?p_j)=c_j?c_i(modm)$$
(pi−pj)∗k+m∗a=cj−ci" role="presentation">(pi?pj)?k+m?a=cj?ci$$(p_i?p_j)?k+m?a=c_j?c_i$$
然后扩欧求出k即可。
我们要求这个方程是否有整数解k" role="presentation">k$k$，并判断是否比min(li,lj)" role="presentation">min(li,lj)$min(l_i,l_j)$小。
然后我们枚举洞数，对于任意两个人之间列一个同余方程，然后求解即可。
代码：

#include 
using namespace std;

int n,pd;
long long c[20],p[20],l[20],m;
inline long long gcd(long long x,long long y)
{
 return y?gcd(y,x%y):x;
}
inline void exgcd(long long a,long long b,long long &x,long long &y)
{
 if(!b)
 {
  x=1;
  y=0;
 }
 else
 {
  exgcd(b,a%b,y,x);
  y-=a/b*x;
 }
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;++i)
 {
  scanf("%lld%lld%lld",&c[i],&p[i],&l[i]);
  m=max(m,c[i]);
 }
 for(int i=m;i<=1e6;++i)
 {
  pd=0;
  for(int j=1;j<=n;++j)
  {
if(pd==1)
break;
for(int k=j+1;k<=n;++k)
{
 long long a=p[j]-p[k],b=i,d=c[k]-c[j],g,x,y;
 if(a<0)
 {
  a=-a;
  d=-d;
 }
 g=gcd(a,b);
 if(d%g)
 continue;
 exgcd(a,b,x,y); 
 x=x*d/g;
 x=(x%(b/g)+(b/g))%(b/g);
 if(!x)
 x+=(b/g);
 if(x<=min(l[j],l[k]))
 {
  pd=1;
  break;
 }
}
  }
  if(!pd)
  {
printf("%d\n",i);
break;
  }
 }
 return 0;
}