BZOJ4602: [Sdoi2016]齿轮 DFS 逆元

这道题就是一个DFS，有一篇奶牛题几乎一样。但是这道题卡精度。

这道题网上的另一篇题解是有问题的。取对数这种方法可以被轻松卡。比如1e18 与 (1e9-1)*(1e9+1）取对数根本无法保证不被卡精度。所以我们需要换一个方法。

我们取一个大质数，在这个质数的模意义下进行运算：乘法是乘法，除法变成乘逆元，负数加一个质数。这种方法虽然可能冲突，但是与数据无关。

#include<cstdio>

using namespace std ;

struct edge {

    int p ;

    int a ;

    int b ;

    edge * next ;

} ;

const int p =  ;

int pow ( int a , int n ) {

    int ans =  ;

    while ( n ) {

        if ( n &  ) ans *= a , ans %= p ;

        a *= a ; a %= p ;

        n /=  ;

    }

    return ans ;

}

int inv ( const int a ) {

    return pow ( a , p -  ) ;

}

const int MAXN =  ;

const int MAXM =  ;

int N , M ;

edge E [ MAXM *  ] ;

edge * V [ MAXN ] ;

bool vis [ MAXN ] ;

int dis [ MAXN ] ;

void read () {

    scanf ( "%d%d" , & N , & M ) ;

    for ( int i =  ; i <= N ; ++ i ) vis [ i ] = V [ i ] =  ;

    while ( M -- ) {

        int s , t , a , b ;

        scanf ( "%d%d%d%d" , & s , & t , & a , & b ) ;

        edge * const t1= & E [ M *  ] ;

        t1 -> p = t ;

        t1 -> a = a ;

        t1-> b = b <  ? b + p : b ;

        t1-> next = V [ s ] ;

        V [ s ] = t1 ;

        edge * const f = & E [ M *  +  ] ;

        f -> p = s ;

        f -> a = b <  ? b + p : b ;

        f -> b = a ;

        f -> next = V [ t ] ;

        V [ t ] = f ;

    }

}

bool dfs ( const int o ) {

    vis [ o ] = true ;

    for ( edge * v = V [ o ] ; v ; v = v -> next )

    if ( ! vis [ v -> p ] ) {

        dis [ v -> p ] = dis [ o ] * v -> a % p * inv ( v -> b ) % p ;

        if ( ! dfs ( v -> p ) ) return false ;

    } else

    if ( dis [ v -> p ] != dis [ o ] * v -> a % p * inv ( v -> b ) % p )

        return false ;

    return true ;

}

bool solve () {

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

    if ( ! vis [ i ] && ( dis [ i ] =  , ! dfs ( i ) ) ) return false ;

    return true ;

}

int main () {

    int T ;

    scanf ( "%d" , & T ) ;

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

        read () ;

        printf ( "Case #%d: " , i ) ;

        puts ( solve () ? "Yes" : "No" ) ;

    }

    return  ;

}