逆元

说明

有的题目要求结果mod一个大质数,如果原本的结果中有除法,比如除以a,那就可以乘以a的逆元替代。

费马小定理求逆元 p为素数

说明

费马小定理求逆元 ax ≡ 1 (mod p) 其中p为质数

复杂度:O(logN)

使用方法

ll ans = inv(a);

模版

const int mod = 1000000009;
long long quickpow(long long a, long long b) {
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
long long inv(long long a) {
    return quickpow(a, mod - 2);
}

扩展欧几里得算法求逆元 a,n互质

说明

扩展欧几里得算法求逆元 ax ≡ 1 (mod n) 其中a,n互质

复杂度:O(logN)

使用方法

ll ans = inv(a, mod);

模版

ll extend_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    else {
        ll r = extend_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}
ll inv(ll a, ll n) {
    ll x, y;
    extend_gcd(a, n, x, y);
    x = (x % n + n) % n;
    return x;
}

逆元线性筛(P为质数)

说明

求1,2,3,…,N关于P的逆元(P为质数)

复杂度:O(N)

使用方法

ll ans = inv(a);

模版

const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;

results matching ""

    No results matching ""