传送
乘法逆元：ax ≡ 1 (mod p)，其中x为a的逆元，求模意义下的乘法逆元，通常有一下几种方法：
1.拓展欧几里得（也就是exgcd）
ax ≡ 1 (mod p)
ax-py=1
这就变成解不定方程的问题了，根据拓展欧几里得算法，代码如下（会TLE3个点）（就算开o2优化也没有卵用）
#include<iostream> #include<cstdio> using namespace std; long long n,p; void exgcd(long long a,long long b,long long &d,long long &x,long long&y)//其中d为a,b的最大公约数 {if(b==0){x=1;y=0;d=a;//当然,exgcd 也可以写成water lift 大佬的有返回值的 } else{ exgcd(b,a%b,d,y,x); y-=a/b*x; } } int main() { cin>>n>>p; for(long long i=1;i<=n;i++) { long long x,y,d; exgcd(i,p,d,x,y); cout<<((x/d)%(p/d)+(p/d))%(p/d)<<endl;//防止x为负数 } }2.费马小定理（因为数据保证p为质数）
a^(p-1) ≡ 1 (mod p)
a*a^(p-2) ≡ 1(mod p)
所以a^(p-2)即为a的逆元。
n个月过后来补个锅（这玩意用快速幂做）
代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int a,p; int ksm(int a,int b,int p) {int r=1; while(b) {if(b&1)r=r*a%p; a=a*a%p; b/=2; } return r; } int main() { scanf("%d%d",&a,&p); cout<<ksm(a,p-2,p); }不过依旧会TLE
3.说了这么多，终于说到不TLE的解法了
那就是线性递推
设p=k*a+r,
k*a+r ≡ 0(mod p)
k*a ≡ -r (mod p)
两边同乘(-r^(-1))*(a^(-1))
k*(-r)^(-1) ≡ a^(-1) (mod p)
即-k*r^(-1) ≡ a^(-1) (mod p)
k=p/a(向下取整)
这样，就得到了a在模p意义下的逆元
递推式 inv[i]=-(p/a)*inv[p%a]%p,
为了让结果不是负数，递推式就变为 inv[i]=(p-p/a)*inv[p%a]%p,
代码如下
#include<iostream> #include<cstdio> using namespace std; long long n,p,f[3000001]; int main() { scanf("%lld %lld",&n,&p);//要用scanf和printf,不然会超时 f[0]=1;f[1]=1; printf("%lld \n",f[1]); for(long long i=2;i<=n;i++) { f[i]=(long long)((p-p/i)*f[p%i])%p; printf("%lld \n",f[i]); } }
转载于:https://www.cnblogs.com/lcez56jsy/p/10560728.html
相关资源：数据结构—成绩单生成器