2019-07-29
这题真的让我发现自己有好多知识盲区 这么菜怎么不去死
知识点:
$(p−1)!≡p−1≡−1 (mod p) $(p is a prime)
* 质数的密度分布
数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系.
什么是逆元
当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:
设c是b的逆元,则有bc≡1(mod m);
则(a/b)%m = (a/b)1%m = (a/b)b c%m = a c(mod m);
即a/b的模等于a b的逆元的模;
逆元就是这样应用的。
逆元的求法有很多
这里用到的是阶乘的逆元
1 2 3 4 5 6 7 8 fac[0 ] = fac[1 ] = 1 ; for (int i = 2 ; i <= MAXN; i++)fac[i] = fac[i - 1 ] * i % mod;inv[MAXN] = quipow(fac[MAXN], mod - 2 ); for (int i = MAXN - 1 ; i >= 0 ; i--)inv[i] = inv[i + 1 ] * (i + 1 ) % mod;
由于计算机底层设计的原因,做加法往往比乘法快的多,因此将乘法转换为加法计算将会大大提高(大
数,比较小的数也没必要)乘法运算的速度,除此之外,当我们计算a*b%mod的时候,往往较大的数计算a*b会超出long long int的范围,这个时候使用快速乘法方法也能解决上述问题.
快速乘法的原理就是利用乘法分配率来将a*b转化为多个式子相加的形式求解(注意这时使用乘法分配 率的时候后面的一个乘数转化为二进制的形式计算).举个栗子
20*14 = 20*(1110)2 = 20*(2^3)*1 + 20*(22)*1+20*(2 1)*1+20*(2^0)*0 = 160+80+40=280.
1 2 3 4 5 6 7 8 9 10 11 12 ll mul (ll a, ll b) { ll res = 0 ; while (b) { if (b & 1 ) res = (res + a) % mod; a = (a + a) % mod; b >>= 1 ; } return res % mod; }
与快乘异曲同工
1 2 3 4 5 6 7 8 9 10 11 12 13 ll mod_pow (ll x, ll n, ll mod) { ll res = 1 ; while (n) { if (n & 1 ) res = (res * x) % mod; x = (x * x) % mod; n >>= 1 ; } return res; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 bool isprime (ll a) { for (int i = 2 ; i * i <= a; i++) { if (a % i == 0 ) { return false ; } } return true ; } void getprime () { for (int i = 2 ; i <= maxn; i++) { if (!vis[i]) { prime[cnt++] = i; } for (int j = 0 ; j < cnt && (ll)i * prime[j] <= maxn; j++) { vis[i * prime[j]] = 1 ; if (i % prime[j] == 0 ) break ; } } }
推导:
由威尔逊:( p − 1 ) ! m o d p = − 1 (p - 1)!mod p = -1 ( p − 1 ) ! m o d p = − 1 ,即( p − 1 ) ! m o d p = p − 1 (p - 1)!mod p = p - 1 ( p − 1 ) ! m o d p = p − 1
所以
Q ! ( m o d p ) = ( p − 1 ) ! ( m o d p ) ( Q + 1 ) × ( Q + 2 ) × … × ( p − 1 ) Q!(mod p)=\frac{(p-1)!(modp)}{(Q+1)\times(Q+2)\times\ldots\times(p-1)} Q ! ( m o d p ) = ( Q + 1 ) × ( Q + 2 ) × … × ( p − 1 ) ( p − 1 ) ! ( m o d p )
步骤:
因为两个素数之间的间隔不会超过300,我们从P-1开始一个个查验找Q。再把(P-1)乘上[Q,P-1]的逆元即可。注意因为数很大,所有涉及乘的地方都要用快速乘。
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <bitset> #include <string> #include <cmath> #include <sstream> using namespace std;typedef long long ll;const double pi = acos (-1.0 );const int eps = 1e-10 ;const int INF = 0x3f3f3f3f ; const int maxn = 1e7 + 10 ;ll mod; int prime[maxn + 10 ], cnt;bool vis[maxn + 10 ];bool isprime (ll x) { for (int i = 0 ; i < cnt && (ll)prime[i] * prime[i] <= x; i++) if (x % prime[i] == 0 ) return 0 ; return 1 ; } bool isprime (ll a) { for (int i = 2 ; i * i <= a; i++) { if (a % i == 0 ) { return false ; } } return true ; } void getprime () { for (int i = 2 ; i <= maxn; i++) { if (!vis[i]) { prime[cnt++] = i; } for (int j = 0 ; j < cnt && (ll)i * prime[j] <= maxn; j++) { vis[i * prime[j]] = 1 ; if (i % prime[j] == 0 ) break ; } } } ll mul (ll a, ll b) { ll res = 0 ; while (b) { if (b & 1 ) res = (res + a) % mod; a = (a + a) % mod; b >>= 1 ; } return res % mod; } ll qpow (ll a, ll b) { ll res = 1 ; while (b) { if (b & 1 ) res = mul (res, a); a = mul (a, a); b >>= 1 ; } return res; } int main () { int t; getprime (); ll p, q; scanf ("%d" , &t); while (t--) { scanf ("%lld" , &p); mod = p; q = p - 1 ; while (!isprime (q)) q--; ll ans = p - 1 ; for (ll i = q + 1 ; i <= p - 1 ; i++) ans = mul (ans, qpow (i, mod - 2 )); printf ("%lld\n" , ans); } return 0 ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include <iostream> #include <iomanip> #include <cmath> #include <map> #include <string> #include <vector> #include <set> #include <algorithm> #include <string.h> using namespace std;typedef unsigned long long ll;ll P; unsigned long long kuai (__int128 a, __int128 b) { __int128 sum = 1 ; a = a % P; while (b > 0 ) { if (b % 2 == 0 ) { a = (a * a) % P; b = b / 2 ; } else { sum = (sum * a) % P; a = (a * a) % P; b = b / 2 ; } } return sum; } bool prime ( long long a) { for (int i = 2 ; i <= sqrt (a); i++) { if (a % i == 0 ) return false ; } return true ; } int main () { int T; __int128 Q, ans; scanf ("%d" , &T); while (T--) { cin >> P; Q = P - 2 ; ans = 1 ; for (int i = 2 ; !prime (Q); Q--, i++) { ans = (ans * kuai (P - i, P - 2 )) % P; } cout << (ll)ans << endl; } }