費馬小定理、擴充歐幾裡得、遞推求解逆元

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
//求解逆元的方法
//費馬小定理求解逆元
//p是質數 a^(p-1)%p==1  a*a^(p-2)%p==1
//						a*a^(-1)%p==1  // a*1/a%p==1
//				''	a的逆元為a^(p-2) 
//方法一 
方法1：費馬小定理：  如果模P是素數的話，那麼inv(a)=pow(a,p-2)%p; 等式右邊用快速幂運算可以得出。
ll poww(ll a,ll b,ll mod)
{
	ll ans = 1;
	while(b)
	{
		if(b&1)
			ans = ans * a % mod;
		b>>=1;
		a = a * a % mod; 
	}
	return ans;
}
ll inv(ll a,ll mod)
{
	return poww(a,mod-2,mod);
	//得到a的逆元 
}

//方法二
//擴充歐幾裡得 
方法1：擴充歐幾裡得。  ax=1(mod P), gcd(a,p)=1， 其中x為a的逆元，就是我們所求，ax=PY+1,   ax-Py=1,  是以用擴充歐幾裡得可以求出x。
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll r =exgcd(b,a%b,x,y);
	ll t=y;
	y=x-(a/b) * y;
	x=t;
	return r;//r是最大公因數/公約數 
}
ll inv(ll a,ll mod)
{
	ll x,y;
	exgcd(a,mod,x,y);
	return (x+mod)%mod;
}
//兩個函數可以得到a在mod下的逆
 

//方法三
//遞推求解逆元//需要求解多個逆元時使用 
方法3：遞推求逆元 inv[i]=(M-M/i)*inv[M%i]%M (其中M為模數，要求為奇質數) 
const int manx = 1e5+10;
ll inv[maxn];

void Prepare_inv(int n,int M)//mod==M求n的逆元 
{
	int v[1]=1;
	for(int i=2;i<=n;i++)
	{
		inv[i]=(ll)(M-M/i)*inv[M%i]%M;
	}
 }

#include<iostream>  
#include<cstdio>  
#include<cstdlib>  
#include<cmath>  
#include<algorithm>  
#include<cstring>  
using namespace std;  
int A[100001];  
int p;  //求出1--p的所有逆元 
int main()  
{  
    cin>>p;  
    A[1]=1;  
    for(int i=2;i<=p;i++)  
    {  
        A[i]=(p-(p/i))*A[p%i]%p;  
      //  printf("%d %d %d\n",i,A[i],(i*A[i])%p);  
    } 
    for(int i=1;i<=p;i++)
    	cout<<A[i]<<endl;
	return 0;		
}