[Acwing] 逆 元 ! !

前言

为什么 我开始学这个呢 https://ac.nowcoder.com/acm/contest/11212/C (因为昨天这题不会优化 还被大佬嘲讽了 哭唧唧 题目来自牛客小白院赛35) (开始和数论队友抢饭碗)

逆元

如果 b 和 m 互质 并且 b|a (b!=a)

使得 a/b == a*x (mod m) 则 称 x 为 b的模m 乘法逆元

记作 b^(-1)(mod m)

(卧槽 好绕)

推导过程

质数 —> 费马定理

如果b和p 是互质的

那么 b^(p-1) == (1 mod p ) 即 b * b^(p-2) == (1 mod p)

则b^(p-2)就是 b 的 mod p 的逆元 | | | V

对应例题

所以这题 就是 a^(p-2) mod p (快速幂)

code

无解情况 b 和 p 不互质 (即 b 和 p成倍数关系 即b mod p != 1)

#include 
#include 

using namespace std;

typedef long long LL;


LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}

应用

• 处理 除法 求余 (a/b == a*x (mod) m 即 a/b == a * b^(-1))