[NOI 2002]Sevege拡張ユークリッド

答えmを列挙すると,同余方程式(Ci−Cj)+x(Pi−Pj)=0(mod m)の無解または最小正整数解がmin(Li,Lj)より大きくなる.注意mはmaxCiから列挙される.誤点:exgcdでy=y-x*(a/b)は最初は括弧を打っていませんでした.コード:

#include
#include
#include
using namespace std;
int n,c[20],p[20],l[20],ans=0;
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0) {x=1;y=0;return a;}
    int re=exgcd(b,a%b,y,x);
    y=y-x*(a/b);
    return re;
}
bool check(int a,int b,int c,int lim)
{
    a=(a%b+b)%b;c=(c%b+b)%b;
    int gcd,x,y;
    gcd=exgcd(a,b,x,y);
    if(c%gcd!=0) return 1;
    b/=gcd;
    x=(x*(c/gcd)%b+b)%b;
    return (x>lim);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&c[i],&p[i],&l[i]);
        ans=max(ans,c[i]);
        c[i]--;
    }
    for(;;ans++)
    {
        bool pd=1;
        for(int i=1;(i<=n)&&pd;i++)
            for(int j=i+1;(j<=n)&&pd;j++)
                pd=pd&&check(p[i]-p[j],ans,c[j]-c[i],min(l[i],l[j]));
        if(pd){printf("%d",ans);break;} 
    }
    return 0;
}