侠客行
#include
void luwei_gcd(int a,int b,int &d,int &x,int &y )
{
if(b==0) //对于ax+by=d且b=0,显然有x=1(因为gcd(a,b) = d,可知a=d)
{
d=a;
x=1;
y=0;
return ;
}
luwei_gcd(b,a%b,d,y,x);//a*x+b*y=d可转化为b*y+(a%b)*(y-x*(a/b))=d
y -= x * (a/b) ;//在回溯时x = y,y = y-x*(a/b),更新x,y的值
}
// ax ≡ 1 (mod n) 满足gcd(a,n) = 1,该问题可化为ax + bn = 1,然后上面的函数，即可求出x
int shuchu (int a ,int n)
{
int d,x,y ;
luwei_gcd(a,n,d,x,y);
if(d==1) //ax + bn = 1
{
x=x%n;
if(x<0)
return (x+n)%n;//返回的值保证是正数
printf("a mod b 的逆元为：%dn",x);
printf("b mod a 的逆元为：%dn",(1-a*(x-26))/n);
}
else
printf("a 与 b 不互素，不存在逆元n");
}

int main()
{
int a,b;
printf("输入两个正整数:(a scanf("%d%d",&a,&b);
shuchu(a,b);
return 0;
}