[2019杭电多校第三场][hdu6608]Fansblog

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6608

大致题意是比p小的最大素数q，求q!%p的值。

由威尔逊定理开始推：

$(p-1)!\equiv-1(mod p)$

$(p-1)!modp\equiv p-1$

$q!*(q+1)*(q+2)*...*(p-1)modp\equiv p-1$

$q!modp=\tfrac{p-1}{(q+1)*(q+2)*...*(p-1)}modp$

然后只需要求出q就可以了，数量级1e9的判断素数可以用Miller_Rabin判断素数。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<vector>

 #include<ctime>

 using namespace std;

 typedef long long ll;

 ll qmul(ll a, ll b, ll mod) {

     ll ans = ;

     while (b) {

         if (b & )

             ans = (ans + a) % mod;

         a = (a << ) % mod;

         b >>= ;

     }

     return ans;

 }

 ll qpow(ll x, ll n, ll mod) {

     ll ans = ;

     while (n) {

         if (n & )

             ans = qmul(ans, x, mod);

         x = qmul(x, x, mod);

         n >>= ;

     }

     return ans;

 }

 bool Miller_Rabin(ll x) { //判断素数

     srand(unsigned(time(NULL)));

     ll s = , t = x - ;

     if (x == )  return true;   //2是素数

     if (x <  || !(x & ))  return false;     //如果x是偶数或者是0,1，那它不是素数

     while (!(t & )) {  //将x分解成(2^s)*t的样子

         s++;

         t >>= ;

     }

     for (int i = ; i < ; ++i) {      //随便选10个数进行测试

         ll a = rand() % (x - ) + ;

         ll b = qpow(a, t, x), k;      //先算出a^t

         for (int j = ; j <= s; ++j) {    //然后进行s次平方

             k = qmul(b, b, x);   //求b的平方

             if (k ==  && b !=  && b != x - )     //用二次探测判断

                 return false;

             b = k;

         }

         if (b != )  return false;   //用费马小定律判断

     }

     return true;   //如果进行多次测试都是对的，那么x就很有可能是素数

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         ll p, q;

         scanf("%lld", &p);

         q = p - ;

         while (!Miller_Rabin(q))

             --q;

         ll ans = p - ;

         for (ll i = p - ; i > q; --i)

             ans = qmul(ans, qpow(i, p - , p), p);

         printf("%lld\n", ans);

     }

     return ;

 }