- int ex_gcd(int a, int b, int &x, int &y) { // 函数返回 gcd(a, b)
- if (b == 0) {
- x = 1, y = 0;
- return a;
- }
- int r = ex_gcd(b, a % b, y, x);
- y -= (a / b) * x;
- return r;
- }
- int main() {
- int a, b, x, y;
- cin >> a >> b; // 求 a 关于模 b 的逆元
- cout << (ex_gcd(a, b, x, y) == 1 ? (x % b + b) % b : -1) << endl; // -1 表示逆元不存在
- return 0;
- }
- View Code
2. 费马小定理:
内容: 假如 a 是一个整数, p 是一个质数, 那么 ap - a 是 p 的倍数, 可以表示为
ap a (mod p)
如果 a 不是 p 的倍数 (即 gcd(a, p) == 1), 这个定理也可以写成
ap-1 1 (mod p)
变形得 a * ap-2 1 (mod p), 所以 a 关于模 p 的逆元 x = ap-2 (mod p), 用快速幂模可快速求之
算法时间复杂度: O(logn)
模板代码:
- LL pow_mod(LL a, LL b, LL p) { //a 的 b 次方取模 p
- LL ret = 1;
- while (b) {
- if (b & 1) ret = (ret * a) % p;
- a = (a * a) % p;
- b >>= 1;
- }
- return ret;
- }
- LL Fermat(LL a, LL p) { // 费马小定理求 a 关于 b 的逆元
- return pow_mod(a, p - 2, p);
- }
- View Code
3. 欧拉定理:
欧拉函数: 对正整数 n, 欧拉函数是小于 n 的正整数中与 n 互质的数的数目 (φ(n) = n(1 1/p1)(1 1/p2)(1 1/pm), pn 为 n 的所有质因数, φ(1) = 1)
欧拉定理: 若 gcd(a, p) = 1, 则 a^φ(p) 1 (mod p)
即 a*a^(φ(p)?1) 1(mod p), 那么 a 关于模 p 的逆元 x = a^(φ(p)?1) (mod p)
(当 p 为素数的时候φ(p)=p-1, 则φ(p)-1=p-2 可以看出欧拉定理是费马小定理的推广)
费马小定理要求模数 p 为素数, 欧拉定理则没有此要求, 但是似乎还有个问题? 如何判断 a 是否有逆元呢?
再求一次 gcd 判断是否互质吗? 这还不如直接用扩展欧几里得算法呢
可以由逆元性质直接检验是否为逆元, 看求出的值 x 与 a 相乘模 p 是否为 1 即可
算法时间复杂度: O(logn)
模板代码:
- #include < iostream > using namespace std;
- typedef long long LL;
- LL euler(LL n) { // 欧拉函数
- LL res = n,
- i;
- for (i = 2; i * i <= n; i++) {
- if (n % i == 0) {
- res = res / i * (i - 1);
- while (n % i == 0) n /= i;
- }
- }
- if (n != 1) res = res / n * (n - 1);
- return res;
- }
- LL pow_mod(LL a, LL b, LL p) { // 快速幂模
- LL ret = 1;
- while (b) {
- if (b & 1) ret = (ret * a) % p;
- a = (a * a) % p;
- b >>= 1;
- }
- return ret;
- }
- int main() {
- LL a,
- p,
- inv;
- cin >> a >> p;
- inv = pow_mod(a, euler(p) - 1, p); // inv 为 a 关于模 p 的逆元
- if (a * inv % p == 1) cout << inv << endl; // 由逆元性质检验逆元是否存在
- else cout << -1 << endl; // 不存在输出 - 1
- return 0;
- }
- View Code
4. O(n) 求 1~n 逆元表
在模质数 p 下, 求 1~n 逆元 (n < p)
inv(a) = (p - p / a) * inv(p % a) % p
证明:
设 x = p % a,y = p / a
于是有 x + y * a = p
(x + y * a) % p = 0
移项得 x % p = (-y) * a % p
- x * inv(a) % p = (-y) % p
- inv(a) = (p - y) * inv(x) % p
于是 inv(a) = (p - p / a) * inv(p % a) % p
模板代码:
- #include < cstdio > const int N = 200000 + 5;
- const int MOD = (int) 1e9 + 7;
- int inv[N];
- int init() {
- inv[1] = 1;
- for (int i = 2; i < N; i++) {
- inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
- }
- }
- int main() {
- init();
- }
- View Code
总结:
1. 逆元求解一般利用扩欧
2. 当模数 p 为质数的时候直接使用费马小定理
3. p 非质数使用欧拉函数 (一般不用)
HDU 1576 -- A/B AC 代码:
- #include < iostream > #define MOD 9973 using namespace std;
- typedef long long LL;
- LL qmod(LL a, LL b) { // 快速幂模
- LL res = 1;
- while (b) {
- if (b & 1) res = res * a % MOD;
- a = a * a % MOD;
- b >>= 1;
- }
- return res;
- }
- int main() {
- int t;
- cin >> t;
- while (t--) {
- int n,
- b;
- cin >> n >> b;
- cout << 1ll * n * qmod(1ll * b, MOD - 2) % MOD << endl; // 费马小定理求 b 的逆元
- }
- return 0;
- }
- View Code
进阶题: HDU 5976 -- Detachment (贪心 + 逆元表 + 前缀和积):
- #include <stdio.h>
- const int maxn = 1e5 + 10;
- const int MOD = 1e9 + 7;
- typedef long long LL;
- LL mul[maxn], sum[maxn], inv[maxn];
- void init() {
- mul[1] = 1;
- sum[1] = 0;
- inv[1] = 1;
- for (int i = 2; i < maxn; i++) {
- sum[i] = sum[i-1] + i;
- mul[i] = (i * mul[i-1]) % MOD;
- inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
- }
- }
- int main() {
- int t, x;
- init();
- scanf("%d", &t);
- while (t--) {
- scanf("%d", &x);
- if (x == 1) { puts("1"); continue; }
- int l = 2, r = maxn, mid, idx;
- while (l <= r) {
- mid = (l + r) / 2;
- if (sum[mid] <= x) idx = mid, l = mid + 1;
- else r = mid - 1;
- }
- int rest = x - sum[idx];
- LL ans = 0;
- if (rest == idx) ans = (mul[idx] * inv[2] % MOD * (idx + 2)) % MOD;
- else ans = mul[idx+1] * inv[idx+1-rest] % MOD;
- printf("%I64d\n", ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2493595.html