乘法逆元 - 版本历史

33DAI：批量导入三三文档

2026-05-20T18:24:14Z

批量导入三三文档

33DAI：/* 扩展欧几里得算法 */

2026-02-25T07:22:03Z

扩展欧几里得算法

←上一版本		2026年2月25日 (三) 07:22的版本
第90行：		第90行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			===通解===

			当求出来一组 <math>Ax+By=C</math> 的解 <math>x_0,y_0</math> 后，通解为：

			* <math>x=x_0+\frac{B}{\gcd(A,B)}k</math>
			* <math>y=y_0-\frac{A}{\gcd(A,B)}k</math>

	==费马小定理求逆元==		==费马小定理求逆元==

33DAI：/* 线性求逆元 */

2026-02-06T07:24:18Z

线性求逆元

←上一版本		2026年2月6日 (五) 07:24的版本
第115行：		第115行：

	==线性求逆元==		==线性求逆元==
			<math>p = \lfloor\frac{p}{i}\rfloor\times i+(p \bmod i)</math>

			在 <math>\bmod p</math> 的意义下

			<math>0 \equiv \lfloor\frac{p}{i}\rfloor\times i+(p \bmod i)</math>

			两边同时乘以 <math>i^{-1}</math>

			<math>0 \equiv \lfloor\frac{p}{i}\rfloor+(p \bmod i)\times i^{-1}</math>

			两边同时乘以 <math>(p \bmod i)^{-1}</math>

			<math>0 \equiv \lfloor\frac{p}{i}\rfloor\times (p \bmod i)^{-1} +i^{-1}</math>

			所以

			<math>i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor\times (p \bmod i)^{-1}</math>


	<syntaxhighlight lang="cpp" line>		<syntaxhighlight lang="cpp" line>

33DAI：/* 阶乘的逆元 */

2026-02-06T07:19:09Z

阶乘的逆元

←上一版本		2026年2月6日 (五) 07:19的版本
第131行：		第131行：
	for (int i = 2; i <= n; i++)		for (int i = 2; i <= n; i++)
	inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
	// 预处理1~~~1000的阶乘的逆元~~		// 预处理1~n的阶乘的逆元
	// invFact[i] = inv[1]inv[2]...inv[i]=invFact[i-1]inv[i]		// invFact[i] = inv[1]inv[2]...inv[i]=invFact[i-1]inv[i]
	invFact[0] = invFact[1] = 1;		invFact[0] = invFact[1] = 1;

2026年2月6日 (五) 07:18 33DAI

2026-02-06T07:18:50Z

@@ 第120行： / 第120行： @@
 for (int i = 2; i <= n; i++)
      inv[i] = (p - p / i) * inv[p % i] % p;
 </syntaxhighlight>
 [[分类:代码模板]]

2026年2月6日 (五) 03:46 33DAI

2026-02-06T03:46:21Z

@@ 第33行： / 第33行： @@
+     }
      return res;
+}
 </syntaxhighlight>
@@ 第45行： / 第100行： @@
+}
 </syntaxhighlight>
 [[分类:代码模板]]

2026年2月6日 (五) 02:19 33DAI

2026-02-06T02:19:59Z

←上一版本		2026年2月6日 (五) 02:19的版本
第45行：		第45行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>
			[[分类:代码模板]]

33DAI：创建页面，内容为“==前置== ===快速幂=== ====递归版==== // a 的 b 次方在模 p 意义下的结果 int quick_pow(int a, int b, int p) { if (b == 0) return 1; int x = quick_pow(a, b / 2, p); if (b % 2 == 0) return x * x % p; return x * x % p * a % p; } ====非递归版==== // a 的 b 次方在模 p 意义下的结果 int quick_pow(int a, int b, int…”

2026-02-06T02:18:59Z

创建页面，内容为“==前置== ===快速幂=== ====递归版==== <syntaxhighlight lang="cpp" line> // a 的 b 次方在模 p 意义下的结果 int quick_pow(int a, int b, int p) { if (b == 0) return 1; int x = quick_pow(a, b / 2, p); if (b % 2 == 0) return x * x % p; return x * x % p * a % p; } </syntaxhighlight> ====非递归版==== <syntaxhighlight lang="cpp" line> // a 的 b 次方在模 p 意义下的结果 int quick_pow(int a, int b, int…”

新页面

==前置==

===快速幂===

====递归版====

<syntaxhighlight lang="cpp" line>
// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
if (b == 0)
return 1;
int x = quick_pow(a, b / 2, p);
if (b % 2 == 0)
return x * x % p;
return x * x % p * a % p;
}
</syntaxhighlight>

====非递归版====

<syntaxhighlight lang="cpp" line>
// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
int res = 1;
while (b > 0)
{
if (b % 2 == 1)
res = res * a % p;
b /= 2;
a = a * a % p;
}
return res;
}
</syntaxhighlight>

==费马小定理求逆元==

<syntaxhighlight lang="cpp" line>
// a 在模 p（质数）意义下的逆元
int inv(int a, int p)
{
return quick_pow(a, p - 2, p);
}
</syntaxhighlight>

乘法逆元 - 版本历史

33DAI：​批量导入三三文档

33DAI：​/* 扩展欧几里得算法 */

33DAI：​/* 线性求逆元 */