求逆元的方法

用于将除法运算转化为乘法运算。

All following methods are all carried out under the condition that there is an inverse element.

Problem :

• Calculating $a$’s inverse element (mod $b$).
• Calculating $n$ inverse elements.

Calculate $gcd(a, b)$ to check if there is an inverse element.

查看代码

bool check (int a, int b)
{
    if (a == 1)
        return true;
    return check(b % a, a);
}

Brute Force

Complexity: $O(n)$ .

查看代码

int inv (int a, int b)
{
    for (int i = 1; ; i++)
        if (i * a % b == 1)
            return i;
}     

Euler Theorem

Complexity: Pretreating $n$ $phi[]s$ : $O(n + \log b)$ ; Calculating one $phi$ : $O(\sqrt b + \log b)$ .

查看代码

void init (int n) // Pretreating n phi[]s 
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            primes[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && primes[j] * i <= n; j++)
        {
            vis[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}
int Phi (int x) //Calculating one phi
{
    int res = x;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        res = res / x * (x - 1);
    return res;
}
int binpow (int x, int k, int mod)
{
    int res = 1 % mod, b = x % mod;
    while (k)
    {
        if (k & 1)
            res = res * b % mod;
           b = b * b % mod;
        k >>= 1;
    }
    return res;
}
int inv (int a, int b)
{
    return binpow(a, phi[b] - 1, b);
}

Fermat’s Little Theorem

Used when $ b \in Primes$ .

Complexity: $O(\log b)$ .

查看代码

int binpow (int x, int k, int mod)
{
    int res = 1 % mod, b = x % mod;
    while (k)
    {
        if (k & 1)
            res = res * b % mod;
           b = b * b % mod;
        k >>= 1;
    }
    return res;
}
int inv (int a, int b)
{
    return binpow(a, b - 2, b);
}

Extended Euclidean Algorithm

Complexity: $O(\log a + \log b)$ .

查看代码

void exgcd (int a, int b, int& x, int& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}
int inv (int a, int b)
{
    int x, y;
    exgcd(a, b, x, y);
    return (x % b + b) % b;
}

Linear Recurrence

Complexity: Pretreating $n$ $inv[]s$ : $O(n)$ ; Calculating one $inv$ : $O(\log a)$ .

查看代码

void init (int n) // Pretreating n inv[]s 
{
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (b - (b / i)) * inv[b % i] % b;
}

查看代码

int inv (int a) //Calculating one inv
{
    if (a == 1)
        return 1;
    return (b - (b / i)) * inv(b % a) % b;
}