逆元

什么是逆元

来自一个大佬的解释，反正我是看懂了。。

乘法逆元：

• 模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。
• 在模n的意义下，a存在逆元的充要条件是**n不等于1，且（a，n）互质。

怎样求逆元？

1. 费马小定理（有限制）
   =》p为素数时，a关于mod p的逆元为a^(p-2)mod p。用快速幂模。
2. 扩展欧几里得算法（普遍适用）
   一篇解释了推导过程的博客

• 给定模数n，求a的逆元
• 即ax=1(mod n)
• =》ax-ny=1
• 所以可用扩展欧几里得， ax+by=gcd（a，b）求逆元，即求x的值。
• 注意：
  存在逆元的判断条件是
  a，m互质。

 if(gcd(a,m) != 1)       //a，m不互质，则不存在逆元
 cout << "Not Exist" << endl;
 else
 {
      ext_gcd(a, m, x, y);
      LL ans = (x<=0) ? (x%m+m) : x;  //有可能x是负数，x要先取模再加
      cout << ans << endl;

看一道题 hdu 1576

1. 题意：给出n(n=A%9973)，求(A/B)%9973。(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
2. 思路：
   用乘法逆元的定义:模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。即变成(A/inv(B))%9973，即(A%9973/inv(B)%9973)%9973。
   所以这道题就是求inv(B)，求B的逆元。
3. 上代码，两种方法都有了

#include <iostream>
#include <cstdio>
#define N 9973
using namespace std;
typedef long long LL;

LL power(LL a, int b, int p)  //要用long long啊啊
{///快速幂模，p为素数时，a关于mod p的逆元为a^(p-2)mod p
    LL ans = 1;   //要用long long啊啊
    while(b > 0)
    {
        if(b&1)  //a是奇数
            ans = ans*a%p;
        b >>= 1;
        a = a*a%p;
    }
    return ans%p;
}

LL ext_gcd(int a, int b, int &x, int &y)
{///扩展欧几里得求逆元，普遍的求法
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = ext_gcd(b, a%b, x, y);
    int temp = x;      //扩展欧几里得的推导
    x = y;
    y = temp - a/b*y;
    return r;
}

int main()
{
    int t,x,y;
    int n, b;
    while(cin >> t)
    {
        while(t--)      //注意看题！别总犯低级错误！
        {
            scanf("%d%d", &n, &b);
            //cout << (n%N*power(b, N-2, N))%N << endl;
            ext_gcd(b, N, x, y);  //N不用加负号
            if(x < 0) x += N;     //要加模的数n，防止是负数
            cout << (n%N*x%N)%N << endl;
        }
    }
    return 0;
}