|
|
| （未显示同一用户的5个中间版本） |
| 第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>
| |
| // a 在模 p（质数） 意义下的逆元
| |
| int inv(int a, int p)
| |
| {
| |
| return quick_pow(a, p - 2, p);
| |
| }
| |
| </syntaxhighlight>
| |
| [[分类:代码模板]] | |