From 225a1551d85423224efb361882500bf720a0bac0 Mon Sep 17 00:00:00 2001
From: orzcyand1317 <36555123+orzcyand1317@users.noreply.github.com>
Date: Sat, 9 Mar 2019 10:30:33 +0800
Subject: [PATCH] Update inverse.md

---
 docs/math/inverse.md | 61 ++++++++++++++++++++++------------------------------
 1 file changed, 26 insertions(+), 35 deletions(-)

diff --git a/docs/math/inverse.md b/docs/math/inverse.md
index 936416df..f2cab998 100644
--- a/docs/math/inverse.md
+++ b/docs/math/inverse.md
@@ -7,16 +7,13 @@
 ### 扩展欧几里得法
 
 ```cpp
-void ex_gcd(int a, int b, int& x, int& y) {
+void exgcd(int a, int b, int& x, int& y) {
   if (b == 0) {
     x = 1, y = 0;
     return;
   }
-  ex_gcd(b, a % b, x, y);
-  int t = x;
-  x = y;
-  y = t - a / b * y;
-  return;
+  exgcd(b, a % b, y, x);
+  y -= a / b * x;
 }
 ```
 
@@ -39,16 +36,14 @@ void ex_gcd(int a, int b, int& x, int& y) {
 代码：
 
 ```cpp
-#define ll long long
-inline ll poW(ll a, ll b) {
-  long long ans = 1;
-  a %= p;
-  while (b) {
-    if (b & 1) ans = ((ans * a) % p + p) % p;
+inline int qpow(long long a, int b) {
+  int ans = 1;
+  a = (a % p + p) % p;
+  for (;b;b >>= 1) {
+    if (b & 1) ans = (a * ans) % p;
     a = (a * a) % p;
-    b >>= 1;
   }
-  return ans % p;
+  return ans;
 }
 ```
 
@@ -68,21 +63,23 @@ inline ll poW(ll a, ll b) {
 
  $i^{-1} \equiv -(\frac{p}{i}) (p \mod i)^{-1}$ ；
 
-然后我们就可以推出逆元了，代码只有一行：
+然后我们就可以推出逆元了，实现代码极短：
 
 ```cpp
-a[i] = -(p / i) * a[p % i];
+inv[1] = 1;
+for(int i = 2;i <= n;++i)
+  inv[i] = (long long)-(p / i) * inv[p % i] % p;
 ```
 
-但是，有些情况下要避免出现负数，所以我们要改改代码，让它只求正整数：
+但是有些情况下这样做会出现负数，所以我们要改改代码，让它只求正整数：
 
 ```cpp
-a[i] = (p - p / i) * a[p % i] % p;
+inv[1] = 1;
+for(int i = 2;i <= n;++i)
+  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
 ```
 
-这就是线性求逆元
-
-
+这就是线性求逆元。
 
 ### 线性求任意 n 个数的逆元
 
@@ -92,9 +89,7 @@ a[i] = (p - p / i) * a[p % i] % p;
 
 因为 $sv_n$ 是 $n$ 个数的积的逆元，所以当我们把它乘上 $a_n$ 时，就会和 $a_n$ 的逆元抵消，于是就得到了 $a_1$ 到 $a_{n-1}$ 的积逆元，记为 $sv_{n-1}$。
 
-同理我们可以依次计算出所有的  $sv_i$。
-
-于是 $a_i^{-1}$ 就可以用 $s_{i-1} \times sv_i​$ 求得。
+同理我们可以依次计算出所有的  $sv_i$，于是 $a_i^{-1}$ 就可以用 $s_{i-1} \times sv_i$ 求得。
 
 所以我们就在 $O(n + \log p)$ 的时间内计算出了 $n$ 个数的逆元。
 
@@ -102,17 +97,13 @@ a[i] = (p - p / i) * a[p % i] % p;
 
 ```cpp
 s[0] = 1;
-for (int i = 1; i <= n; ++i) {
-    s[i] = s[i - 1] * a[i] % kcz;
-}
-sv[n] = qpow(s[n]); //求逆元
-for (int i = n; i >= 1; --i) {
-    sv[i - 1] = sv[i] * a[i] % kcz;
-}
-LL ans=0;
-for (int i = 1; i <= n; ++i) {
-    av[i]=sv[i] * s[i - 1] % kcz;
-}
+for (int i = 1; i <= n; ++i)
+    s[i] = s[i - 1] * a[i] % p;
+sv[n] = qpow(s[n], p - 2);
+for (int i = n; i >= 1; --i)
+    sv[i - 1] = sv[i] * a[i] % p;
+for (int i = 1; i <= n; ++i)
+    inv[i] = sv[i] * s[i - 1] % p;
 ```
 
 
-- 
2.11.0