51nod 1256乘法逆元（含费马小定理的解释及证明）

51nod 1256乘法逆元（含费马小定理的解释及证明）

解释及证明：

.html 

51nod 1256：

1256 乘法逆元

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题

 收藏

 关注

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input

输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)

Output

输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input示例

2 3

Output示例

2

快速幂：

#include<cstdio>
#include<cstring>
int phi;
long long int mod;
long long int poww(long long int a)
{int b=phi-1;long long ans=1;while(b) {if(b&1) ans=ans*a%mod;b=b>>1;a=a*a%mod;}return ans;
}
int getphi(int x)
{int sum=x;for(int i=2;i*i<=x;i++){if(x%i==0){sum=sum/i*(i-1);while(x%i==0) x/=i;}}if(x>1) sum=sum/x*(x-1);return sum;
}
int main()
{long long int a;scanf("%lld %lld",&a,&mod);   phi=getphi(mod);long long  ans=poww(a);printf("%lld",ans);return 0;
}

exgcd：

#include <stdio.h>
#include <stdlib.h>
#define ll long long
ll e_gcd(ll a,ll b,ll &x,ll &y)
{ll ans,p;if(b==0){x=1,y=0;return a;}ans=e_gcd(b,a%b,x,y);p=x;x=y;y=p-a/b*y;return ans;
}
int main()
{long long m,n,c,d,e,q;while(scanf("%lld %lld",&m,&n)!=EOF){c=e_gcd(m,n,d,e);q=(d%n+n)%n;printf("%lldn",q);}return 0;
}

#include<cstdio>
void gcd(int a,int b,int &x,int &y)
{if(b==0){x=1;y=0;return;}gcd(b,a%b,y,x); //不明处y=y-a/b*x; //不明处
}
int main()
{int m,n,x,y;scanf("%d%d",&m,&n);gcd(m,n,x,y);printf("%dn",(x%n+n)%n);
}

对于不明处的理解:

可以找到x,y,使得ax + by=c成立；

//这部分相当于依着gcd(b,a%b,y,x)推

如果找到x',y',使得下面的等式成立

by'+(a%b)x'=c   

也就是

by'+(a-a/b*b)x'=c  

也就是

ax'+b(y'-[a/b]x')=c

所以

x=x',y=y'-[a/b]x'

可以得到x与x'是相等的，只需改变y  ----对应的就是代码中y=y-a/b*x;