乘法逆元（擴充套件歐幾里得)||((費馬小定理||尤拉定理)+快速冪)||(線性遞推）
摘要：
定義
若，且與互質，則稱為的逆元，記為。
如何求？
1.擴充套件歐幾里德演算法
若
使用擴充套件歐幾里德演算法求解即可，速度較慢。
//1.exgcd
#include <cstdio>
#include <iostream>
u...
定義
若，且與互質，則稱為的逆元，記為。
如何求？
1.擴充套件歐幾里德演算法
若
Line"/>
使用擴充套件歐幾里德演算法求解即可，速度較慢。
//1.exgcd
#include <cstdio>
#include <iostream>
using namespace std;
int n,p,x,y;
void exgcd(int a,int b,int& x,int& y)
{
if(b==0)
{
x=1;y=0;
return ;
}
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
int main()
{
scanf("%d %d",&n,&p);
for(int i=1;i<=n;i++)
{
exgcd(i,p,x,y);
printf("%d\n",(x%p+p)%p);
}
return 0;
}
2.快速冪
費馬小定理
內容：如果,互質，那麼。
在這個定理的基礎上，可以使用費馬小定理來推出求解公式。
首先，因為
又因為
故
根據同餘的性質,若為質數,得到