由AtCoder_ABC357D引发的除法同余学习

鉴于最近的Atcoder周赛又出现除法求余，下定决心学习逆元相关内容

同余概述

定义

同余定义：若a和b是整数，且m | (a - b),则称a和b模m同余。即两者除以m得到的余数相同。

剩余系：一个模m完全剩余系是一个整数集合，任何一个整数恰好与该集合中的一个元素模m同余。例如0,1,...,m-1的集合是模m完全剩余系。

逆

求解同余方程\(ax\equiv b(mod\ m)\)需要用到逆

逆的概念

给定整数a，并且满足\(gcd(a,m) = 1\),称 \(a * x \equiv 1 (mod \ m)\)的一个解为a模m的逆，记为\(a^{-1}\)

即a的x倍模m的结果等于1，对应的x记为a模m的逆

《算法竞赛》书上的逆元部分太难了，直接跑路，选择左神视频速成除法同余

除法同余

求\((a/ b) mod \ MOD\)的结果

需要满足的条件

1. \(a / b\)在每次存在除法的时候都可以整除
2. 保证MOD是质数以满足费马小定理
3. 保证b和MOD的最大公约数为1

除法同余的结论

1. 求\(\frac{1}{b}\)关于MOD的同余数，也就是b的逆元，将除法同余转化为乘法同余
2. 使用费马小定理求b的逆元，\(inv[b] = b^{MOD-2}\ \% \ MOD\)
3. 得到对应的结果 \((a/ b) \% MOD = ((a \% MOD) * inv[b])\%MOD\)

除法同余所用到的快速幂

define ll long long;
ll fast_pow(ll x, ll y, int m) {
	ll res = 1;
	while (y) {
		if (y & 1) res *= x, res %= m;
		x = (x * x) % m;
		y >>= 1;
	}
	return res;
}
long long mod_inverse(long long a, long long mod) {
	return fast_pow(a, mod - 2, mod);
}

该题解的起源abc357D的示例代码

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int mod = 998244353;  
ll n;  
ll fast_pow(ll b, ll p, ll m) {  
    ll res = 1;  
    while (p) {  
        if (p & 1) res *= b, res %= m;  
        p >>= 1;  
        b = (b * b) % m;  
    }  
    return res;  
}  
ll cacu_inv(ll a, ll m) {  
    return fast_pow(a, m - 2, m);  
}  
int main() {  
    cin >> n;  
    int w = 0;  
    ll tmp = n;  
    while (tmp) {  
        w++;  
        tmp /= 10;  
    }  
    ll base = fast_pow(10, w, mod);  
    ll res = ((fast_pow(base, n, mod)+ mod - 1) % mod) * cacu_inv((base + mod - 1) % mod, mod)  % mod;  
    //注意n的范围[1,1e18]同样需要除余  
    cout << (res * (n % mod)) % mod;  
    return 0;  
}

连续数字逆元的线性递推

例题P3811

在\(\% p\)的意义下，求\(1,2,3,...n\)中每个数的逆元
\(inv[1] = 1\)
\(inv[i] = (int)(p - (long)inv[p \% i] * (p / i)\%p\)

连续阶乘逆元的线性递推

求组合数的逆元

先求\(n!\)乘法同余的结果，假设为\(a\)，然后求\(a\)的逆元，假设为\(b\)
\(inv[n] = b\)
\(inv[i] = ((long)(i + 1) * inv[i + 1])\% MOD\)