什么是逆元
來自一個大佬的解釋照捡，反正我是看懂了。话侧。
乘法逆元：
- 模p意義下栗精，一個數(shù)a如果有逆元x，那么除以a相當于乘以x瞻鹏。
- 在模n的意義下悲立，a存在逆元的充要條件是**n不等于1，且（a新博，n）互質(zhì)薪夕。
怎樣求逆元？
-
費馬小定理（有限制）
=》p為素數(shù)時赫悄，a關(guān)于mod p的逆元為a^(p-2)mod p原献。用快速冪模馏慨。 -
擴展歐幾里得算法（普遍適用）
一篇解釋了推導(dǎo)過程的博客
- 給定模數(shù)n，求a的逆元
- 即ax=1(mod n)
- =》ax-ny=1
- 所以可用擴展歐幾里得姑隅， ax+by=gcd（a写隶，b）求逆元，即求x的值讲仰。
-
注意：
存在逆元的判斷條件是
a慕趴，m互質(zhì)。
if(gcd(a,m) != 1) //a叮盘，m不互質(zhì)秩贰，則不存在逆元
cout << "Not Exist" << endl;
else
{
ext_gcd(a, m, x, y);
LL ans = (x<=0) ? (x%m+m) : x; //有可能x是負數(shù)，x要先取模再加
cout << ans << endl;
看一道題 hdu 1576
- 題意：給出n(n=A%9973)柔吼，求(A/B)%9973毒费。(我們給定的A必能被B整除，且gcd(B,9973) = 1)愈魏。
-
思路：
用乘法逆元的定義:模p意義下觅玻，一個數(shù)a如果有逆元x，那么除以a相當于乘以x培漏。即變成(A/inv(B))%9973溪厘，即(A%9973/inv(B)%9973)%9973。
所以這道題就是求inv(B)牌柄，求B的逆元畸悬。 - 上代碼，兩種方法都有了
#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為素數(shù)時蹋宦，a關(guān)于mod p的逆元為a^(p-2)mod p
LL ans = 1; //要用long long啊啊
while(b > 0)
{
if(b&1) //a是奇數(shù)
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; //擴展歐幾里得的推導(dǎo)
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; //要加模的數(shù)n，防止是負數(shù)
cout << (n%N*x%N)%N << endl;
}
}
return 0;
}
