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

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 #include<ctime>
 8 using namespace std;
 9 typedef long long ll;
10 ll qmul(ll a, ll b, ll mod) {
11     ll ans = 0;
12     while (b) {
13         if (b & 1)
14             ans = (ans + a) % mod;
15         a = (a << 1) % mod;
16         b >>= 1;
17     }
18     return ans;
19 }
20 ll qpow(ll x, ll n, ll mod) {
21     ll ans = 1;
22     while (n) {
23         if (n & 1)
24             ans = qmul(ans, x, mod);
25         x = qmul(x, x, mod);
26         n >>= 1;
27     }
28     return ans;
29 }
30 bool Miller_Rabin(ll x) { //判断素数 
31     srand(unsigned(time(NULL)));
32     ll s = 0, t = x - 1;
33     if (x == 2)  return true;   //2是素数 
34     if (x < 2 || !(x & 1))  return false;     //如果x是偶数或者是0,1，那它不是素数 
35     while (!(t & 1)) {  //将x分解成(2^s)*t的样子 
36         s++;
37         t >>= 1;
38     }
39     for (int i = 0; i < 10; ++i) {      //随便选一个素数进行测试 
40         ll a = rand() % (x - 1) + 1;
41         ll b = qpow(a, t, x), k;      //先算出a^t
42         for (int j = 1; j <= s; ++j) {    //然后进行s次平方 
43             k = qmul(b, b, x);   //求b的平方 
44             if (k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
45                 return false;
46             b = k;
47         }
48         if (b != 1)  return false;   //用费马小定律判断 
49     }
50     return true;   //如果进行多次测试都是对的，那么x就很有可能是素数 
51 }
52 int main() {
53     int t;
54     scanf("%d", &t);
55     while (t--) {
56         ll p, q;
57         scanf("%lld", &p);
58         q = p - 1;
59         while (!Miller_Rabin(q))
60             --q;
61         ll ans = p - 1;
62         for (ll i = p - 1; i > q; --i)
63             ans = qmul(ans, qpow(i, p - 2, p), p);
64         printf("%lld\n", ans);
65     }
66     return 0;
67 }