淺談模質數意義下的乘法逆元
- 2019 年 10 月 3 日
- 筆記
參考文章www.luogu.org/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan
什麼是乘法逆元
若整數(b,m)互質，並且(b|a)，若存在一個整數(x)，使得(a / b equiv a ast x (mod text{ } m))，稱(x)為 (b)的模(m)乘法逆元。
乘法逆元的用處
有時候，我們需要求(a/b text{ } mod text{ } p)，用樸素的方法，我們只能在(a)上不斷加(p)，直到它能被 bb 整除為止，當(a,b,p)都很大的時候，自然是涼涼了。這時，我們就可以用逆元方便的求解了。
乘法逆元的求法
進入到了本文最關鍵的部分，如何求乘法逆元?
費馬小定理
費馬小定理：當(p)是質數的時候，$a^{p-1} equiv 1 (mod text{ } p) $
那麼將(a^{p-1})拆開來，就得到了(a ast a^{p-2} equiv (mod text{ } p))
所以，(a^{p-2})就是(a)模(p)意義下的乘法逆元。
缺點：用快速冪計算，當(p)比較大的時候，速度比較慢。
程式碼：
#include <algorithm> #include <cstdio> #include <iostream> using namespace std; typedef long long ll; ll n, p; ll ksm(ll a, ll b) { ll ans = 1; for (; b; b >>= 1) { if (b & 1) ans = ans * a % p; a = a * a % p; } return ans; } int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> n >> p; for (int i = 1; i <= n; ++i) { printf("%lldn", ksm(i, p - 2)); } return 0; }擴展歐幾里得演算法
求(a ast x equiv 1 (mod text{ } m))的解(inv(x))，等價於求解(a ast x + b ast y =1)。用擴展歐幾里得演算法求出一組特解(x_0, y_0)，則(x_0)是原方程的一個解，而方程的通解則為所有模(m)與(x_0)同餘的整數，通過取模操作把解的範圍移動到(1～p)之間即可。
程式碼：
#include <algorithm> #include <cmath> #include <iostream> using namespace std; typedef long long ll; ll n, p; void exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return; } exgcd(b, a % b, x, y); ll z = x; x = y, y = z - y * (a / b); return; } int main() { cin >> n >> p; for (int i = 1; i <= n; ++i) { ll x, y; exgcd(i, p, x, y); x = (x % p + p) % p; cout << x << endl; } return 0; }線性遞推（可以求多個）
這是一個神奇的過程……
假設我們現在要求(k)的乘法逆元，
令 (a ast k + b = p)
[b ast inv(b) equiv 1 (mod text{ } p)]
把(b=p-aast k)代入，可以得到
[(p-ak)ast inv(b) equiv 1 (mod text{ } p)]
那麼
[p ast inv(b) – a ast k ast inv(b) equiv 1 (mod text{ } p)]
在((mod text{ } p))的意義下，(p equiv 0 (mod text{ } p))，所以(p ast inv(b))可以直接去掉
[-a ast k ast inv(b) equiv 1 (mod text{ } p)]
觀察(a ast k + b = p)可以發現，(a=lfloor p/k rfloor)，(b=p mod k)
[-(p/k) ast inv(p text{ } mod text{ } k) ast k equiv 1 (mod text{ } p)]
即
[-(p/k) ast inv(p text{ } mod text{ } k) equiv inv(k) (mod text{ } p)]
這樣，我們就得了遞推式，在實際的程式碼實現中得加上 (p) 來去掉負號，也就是
[(p-p/k) ast inv(p text{ } mod text{ } k) equiv inv(k) (mod text{ } p)]
程式碼：
#include <algorithm> #include <cmath> #include <cstdio> #include <iostream> using namespace std; typedef long long ll; ll n, p, inv[maxn]; int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> n >> p; inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (ll)(p - p / i) * inv[p % i] % p; for (int i = 1; i <= n; ++i) printf("%lldn", inv[i]); return 0; }