本篇介绍线性求逆元的推导过程
·对于一个质数\(P\),我们需要求出\(1-N\)在\(mod\ P\)意义下的逆元,如何使用线性的方法求其逆元呢?
·首先,我们设\(t=P/i,k=P\%i\);
·对于\(i*t+k≡0 \pmod{P}\),我们可以做出如下推导:
·等式两边同时除以\(i*k\),我们可以得到新式子\(\frac{t}{k}+\frac{1}{i}≡0 \pmod{P}\);
·从而得到:\(\frac{P}{i}*inv[P\%i]+inv[i]≡0 \pmod{P}\);
·最后得到\(inv[i]=(-\frac{P}{i}+P)*inv[P\%i]%P\);
\(code:\)
#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=(1e7*2)+2;
ll n,p,inv[maxn];
inline ll add(ll a,ll b){return a+b<p?a+b:a+b-p;}
inline ll mul(ll a,ll b){return a*b<p?a*b:a*b%p;}
int main()
{
scanf("%lld%lld",&n,&p);inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=mul(add(-p/i,p),inv[p%i]);
}
转载于:https://www.cnblogs.com/KatouKatou/p/9821642.html
相关资源：各显卡算力对照表！
