乘法逆元求法
原创建时间：2018-08-05 08:24:19
数论中的重要内容
注意：本文只讨论模数为质数的情况，因为当模数为合数时，不一定所有数都有逆元
定义
在\(\bmod\ p\)的意义下，我们把\(x\)的乘法逆元写作\(x^{-1}\)。乘法逆元有这样一条性质：
\[x \times x^{-1} \equiv 1\ (\bmod\ p)\]
乘法逆元有什么用呢？
模意义下的除法运算！
除法运算对于模运算来说并不是「封闭」的，所以我们可以把除法转化成乘法
费马小定理求法
前置知识：「快速幂」
\(a^{p-1} \equiv 1 (\bmod\ p)%\)
经过变形，可得
\(a \times a^{p-2} \equiv 1(\bmod\ p)\)
由定义可得，\(a\)的乘法逆元就是\(a^{p-2}\)
这就要用到「快速幂」
inline int slowPower(int a, int b, int p) {
int ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return ans;
}
inline int invMod(int x, int p) {
return slowPower(x, p - 2, p);
}代码实现
输出1到n的逆元
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>
/* -- External Headers -- */
#include <map>
#include <cmath>
/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
namespace FastIO {
inline long long int getint() {
long long int s = 0, x = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') x = -1;
ch = getchar();
}
while (isdigit(ch)) {
s = s * 10ll + ch - '0';
ch = getchar();
}
return s * x;
}
inline void __basic_putint(long long int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) __basic_putint(x / 10);
putchar(x % 10 + '0');
}
inline void putint(long long int x, char external) {
__basic_putint(x);
putchar(external);
}
}
namespace Solution {
const int MAXN = 5000000 + 10;
long long int n, k, HA, a[MAXN];
long long int fac[MAXN], invf[MAXN];
long long int SlowPower(long long int a, long long int x) {
// a^x mod m
long long int ret = 1;
if (x == 1) return a;
while (x) {
if (x & 1) ret = ret * a % HA;
a = a * a % HA;
x >>= 1;
}
return ret;
}
}
signed main() {
using namespace Solution;
using namespace FastIO;
n = getint(); HA = getint();
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = (fac[i - 1] * i) % HA;
}
invf[n] = SlowPower(fac[n], HA - 2);
for (long long int i = n - 1; i >= 1; --i) {
invf[i] = (invf[i + 1] * (i + 1)) % HA;
}
for (long long int i = 1; i <= n; ++i) {
printf("%lld\n", (invf[i] * fac[i - 1]) % HA);
}
return 0;
}
1、CSS布局口诀 - CSS BUG顺口溜
2、linux 常用命令
3、hdoj-1312-Red and Black
4、10.23
5、Django框架——模型(models)层之ORM查询(二)