hdu 5391素数試験

問題の意味は(n-1)!(mod n)の値
ウィルソンの定理によると:
(n−1)!=−1(modn)[n==prime]
だから素数ならば、直接-1に等しくて、素数でなければ、明らかに答えは0であるべきで、nが合数であれば、明らかに1からn-1の中で必ずnのすべての因数が現れるので、特判4に注意して、答えは2です

#include 
#include 
#include 
using namespace std;
long long a[10]={0,2,3,5,7};
long long fast_pow( long long BASE, long long pr, long long mod ) {
    long long x = 1, y = BASE;
    while( pr ) {
        if( pr & 1 ) x = x * y % mod;
        pr >>= 1;
        y = y * y % mod;
    }
    return x % mod;
}
bool miller_rabin( int n ) {
    if( n == 2 || n == 3 || n == 5 || n == 7 ) return true;
    if( n % 2 == 0 ) return false;
    for( register int i = 1; i <= 4; i++ ){
        long long y = a[i];
        long long x = fast_pow( y, n-1, n );
        if( x != 1 ) return false;
    }
    return true;
}
int main() { int T;
    scanf( "%d", &T );
    while( T-- ) { int n;
        scanf( "%lld", &n );
        if( n == 4 ) { printf( "2
" ); continue; }
        if( miller_rabin( n ) ) {
            printf( "%lld
" , n - 1 );
        } else {
            printf( "0
" );
        }
    }
    return 0;
}