BZOJ-1407: [Noi2002]Savage（拓展欧几里

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1407

暴力枚举m，然后暴力枚举每一对(i,j)的野人，用拓展欧几里德算出他们会不会相遇。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

typedef int ll ;

 

const ll maxn = 16 ;

 

ll n , p[ maxn ] , c[ maxn ] , l[ maxn ] ;

 

inline ll gcd( int x , int y ) {

    if ( x < y ) swap( x , y ) ;

    for ( ll z ; y ; z = y , y = x % y , x = z ) ;

    return x ;

}

 

void exgcd( ll a , ll b , ll &x , ll &y ) {

    if ( ! b ) {

        x = 1 , y = 0 ; return ;

    }

    ll tx , ty ; exgcd( b , a % b , tx , ty ) ;

    x = ty , y = tx - ( a / b ) * ty ;

}

 

inline bool check( ll i , ll j , ll m ) {

    if ( c[ i ] < c[ j ] ) swap( i , j ) ;

    ll A = ( p[ j ] - p[ i ] ) , B = m , C = c[ i ] - c[ j ] , v , g ;

    if ( A < 0 ) {

        A = - A , v = -1 ;

    } else v = 1 ;

    g = gcd( A , B ) ;

    if ( C % g ) return false ;

    ll x , y ;

    if ( A > B ) exgcd( A / g , B / g , x , y ) ; else exgcd( B / g , A / g , y , x ) ;

    x *= v , x *= ( C / g ) ;

    if ( x > 0 ) x %= ( B / g ) ;

    if ( x < 0 ) x += ( ( - x ) / ( B / g ) + ( ( - x ) % ( B / g ) > 0 ) ) * ( B / g ) ;

    return x <= l[ i ] && x <= l[ j ] ;

}

 

int main(  ) {

    scanf( "%d" , &n ) ;

    ll maxc = 0 ;

    for ( ll i = 0 ; i ++ < n ; ) {

        scanf( "%d%d%d" , c + i , p + i , l + i ) ;

        maxc = max( maxc , c[ i ] -- ) ;

    }

    for ( ll m = maxc ; ; ++ m ) {

        bool flag = true ;

        for ( ll i = 1 ; i < n ; ++ i ) {

            for ( ll j = i + 1 ; j <= n ; ++ j ) if ( check( i , j , m ) ) {

                flag = false ; break ;

            }

            if ( ! flag ) break ;

        }

        if ( flag ) {

            printf( "%d\n" , m ) ; break ;

        }

    }

    return 0 ;

}