|
|
| （未显示同一用户的1个中间版本） |
| 第1行： |
第1行： |
| ==前置==
| | #REDIRECT [[06-数学相关/04-乘法逆元]] |
| | | [[Category:三三文档]] |
| ===快速幂===
| |
| | |
| ====递归版====
| |
| | |
| <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>
| |
| // 返回 ax+by=gcd(a,b) 的解 <x,y>
| |
| pair<int, int> exGCD(int a, int b)
| |
| {
| |
| // ax+0y=a
| |
| if (b == 0)
| |
| return {1, 0};
| |
| pair<int, int> nxt = exGCD(b, a % b);
| |
| int xx = nxt.first;
| |
| int yy = nxt.second;
| |
| int x = yy;
| |
| int y = xx - a / b * yy;
| |
| return {x, y};
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ====简化一点的写法====
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| // 返回 ax+by=gcd(a,b) 的解 <x,y>
| |
| pair<int, int> exGCD(int a, int b)
| |
| {
| |
| // ax+0y=a
| |
| if (b == 0)
| |
| return {1, 0};
| |
| pair<int, int> nxt = exGCD(b, a % b);
| |
| return {nxt.second,
| |
| nxt.first - a / b * nxt.second};
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ====常见的写法====
| |
| | |
| 返回 gcd，引用类型的参数传递解
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| int exGcd(int a, int b, int &x, int &y)
| |
| {
| |
| if (b == 0)
| |
| {
| |
| x = 1, y = 0;
| |
| return a;
| |
| }
| |
| int xx, yy;
| |
| int gcd = exGcd(b, a % b, xx, yy);
| |
| x = yy;
| |
| y = xx - (a / b) * yy;
| |
| return gcd;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==费马小定理求逆元==
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| // a 在模 p（质数） 意义下的逆元
| |
| int inv(int a, int p)
| |
| {
| |
| return quick_pow(a, p - 2, p);
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==扩欧求逆元==
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| // a 在模 b 意义下的逆元（gcd(a,b)==1）
| |
| int inv(int a, int b)
| |
| {
| |
| pair<int, int> ans = exGCD(a, b);
| |
| // a * ans.first + b * ans.second = 1
| |
| // a * ans.first === 1 (%b)
| |
| return (ans.first % b + b) % b;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==线性求逆元==
| |
| <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>
| |
| inv[1] = 1;
| |
| for (int i = 2; i <= n; i++)
| |
| inv[i] = (p - p / i) * inv[p % i] % p;
| |
| </syntaxhighlight>
| |
| | |
| ==阶乘的逆元==
| |
| | |
| <math>(i!)^{-1}=1^{-1}\times 2^{-1} \times \dots\times i^{-1}</math>
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| // 预处理1~n的逆元
| |
| inv[1] = 1;
| |
| for (int i = 2; i <= n; i++)
| |
| inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
| |
| // 预处理1~n的阶乘的逆元
| |
| // invFact[i] = inv[1]*inv[2]*...*inv[i]=invFact[i-1]*inv[i]
| |
| invFact[0] = invFact[1] = 1;
| |
| for (int i = 2; i <= n; i++)
| |
| invFact[i] = invFact[i - 1] * inv[i] % MOD;
| |
| </syntaxhighlight>
| |
| | |
| | |
| [[分类:代码模板]] | |