乘法逆元的n种解法

Rising_Date苣佬讲解

    我们学着只争朝夕。

    人生苦短，

    道路漫长，

    我们走向并珍爱每一处风光，

    我们不停地走着，

    不停地走着的我们也成了一处风光。

法一：线性递推

#include<bits/stdc++.h>
#define N 3000010
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
using namespace std;
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)-(c^48);c=getchar();}x=f?x:-x;}

ll inv[N],n,p;//不开long long 见祖宗 
int main()
{
	rd(n),rd(p) ;
	inv[1]=1;
	puts("1");
    rep(i,2,n)
	{
        inv[i]=(ll)p-(p/i)*inv[p%i]%p;
//		inv[i]=(ll)(p-(p/i))*inv[p%i]%p;这样写也可以 
		/*我们需要保证i^-1>0所以,我们在右边 +p而且for循环要从2开始，防止改变inv[1]的值;*/
        printf("%lld
",inv[i]);
    }
	return 0;
}

法*【阶乘求逆元】

讲解

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)-(c^48);c=getchar();}x=f?x:-x;}
#define ll long long

ll n,p;
ll fac[3000006],ans[3000006];

ll ksm(ll x,ll power)
{
	ll ans=1;
	for(;power;power>>=1,(x*=x)%=p)
		if(power&1)
			(ans*=x)%=p;
	return ans%p;
} 

int main()
{
	rd(n),rd(p);
    fac[0]=1;
    rep(i,1,n)fac[i]=(fac[i-1]*i)%p;
    ll last=ksm(fac[n],p-2);
    dwn(i,n,1)
    {
		ll k;
        k=(last*i)%p;
        ans[i]=(last*fac[i-1])%p;
        last=k;
    }
    rep(i,1,n)
        printf("%lld
",ans[i]);
    return 0;
}

法2：费马小定理【会t】

#include<bits/stdc++.h>
#define N 3000010
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)-(c^48);c=getchar();}x=f?x:-x;}

int n,p;

ll ksm(ll x,ll power)
{
	ll ans=1;
	for(;power;power>>=1,(x*=x)%=p)
		if(power&1)
			(ans*=x)%=p;
	return ans%p;
}

int main()
{
	rd(n),rd(p);
	rep(i,1,n)
        printf("%d
",ksm(i,p-2));
    return 0;
}

法3：解不定方程（exgcd）【会t】

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)-(c^48);c=getchar();}x=f?x:-x;}
#define ll long long
ll x,y,n,p;

void exgcd(ll a,ll b,ll &x,ll &y) 
{
	if(!b)x=1,y=0;
	else{exgcd(b,a%b,y,x);y-=a/b*x;}
}

int main()
{
	rd(n),rd(p);
	rep(i,1,n)
	{
		exgcd(i,p,x,y);
		printf("%lld
",(x%p+p)%p);
	}
    return 0;
}