线性求逆元算法"/>
线性求逆元算法
摘自:
其实有些题需要用到模的所有逆元,这里为奇质数。那么如果用快速幂求时间复杂度为,
如果对于一个1000000级别的素数,这样做的时间复杂度是很高了。实际上有的算法,有一个递推式如下
它的推导过程如下,设,那么
对上式两边同时除,进一步得到
再把和替换掉,最终得到
初始化,这样就可以通过递推法求出模素数的所有逆元了。
另外模的所有逆元值对应中所有的数,比如,那么对应的逆元是。
附上我自己的代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int A[100001];
int p;
int main()
{cin>>p;A[1]=1;for(int i=2;i<=10;i++){A[i]=(p-(p/i))*A[p%i]%p;printf("%d %d %d\n",i,A[i],(i*A[i])%p);}
}
更多推荐
线性求逆元算法
发布评论