【BZOJ 1407】[Noi2002]Savage ExGCD

我bitset+二分未遂后就来用ExGCD了，然而这道题的时间复杂度还真是玄学......

我们枚举m然后对每一对用ExGCD判解，我们只要满足在最小的一方死亡之前无解就可以了，对于怎么用，就是ax+by=c，在这里c是距离差，a是速度差，b是m，x是我们要的解，y随意。

时间复杂度O(m*n*n*log)，然而这是标解..........

#include <cstdio>

int prob[][],len,n,c[],p[],l[],S;

inline int Min(int x,int y){

  return x<y?x:y;

}

inline int Max(int x,int y){

  return x>y?x:y;

}

inline int GCD(int x,int y){

  return x==?y:GCD(y%x,x);

}

void ExGCD(int a,int &x,int b,int &y){

  if(!b){

    x=,y=;

    return;

  }

  ExGCD(b,x,a%b,y);

  int temp=x;

  x=y,y=temp-a/b*y;

}

int main(){

  freopen("savage.in","r",stdin);

  freopen("savage.out","w",stdout);

  scanf("%d",&n);

  for(int i=;i<=n;i++)

    scanf("%d%d%d",&c[i],&p[i],&l[i]);

  for(int i=;i<=n;i++){

    for(int j=i+;j<=n;j++){

      prob[++len][]=c[i]-c[j],

      prob[len][]=p[j]-p[i],

      prob[len][]=Min(l[i],l[j]);

      if(prob[len][]<)

        prob[len][]*=-,prob[len][]*=-;

    }

    S=Max(S,c[i]);

  }

  for(int m=S;m<=;m++){

    bool god=;

    for(int i=;i<=len;i++){

      int gcd=GCD(prob[i][],m);

      if(prob[i][]%gcd==){

        int x,y;

        ExGCD(prob[i][],x,m,y);

        x=x*prob[i][]/gcd;

        int t=m/gcd;

        x=(x%t+t)%t;

        if(x<=prob[i][]){

          god=;

          break;

        }

      }

    }

    if(god){

      printf("%d",m);

      return ;

    }

  }

}