如何通过扩展欧几里德算法求解nyoj1235 AB问题的逆元？

本文共计519个文字，预计阅读时间需要3分钟。

题目要求我们改写伪原创的代码开头内容，限制不超过100字，不使用重复词汇。

原文：1000+ms | 内存限制：65535 | 描述：已知：1.n=(A % 9973); 2.gcd(B, 9973)=1; 计算：(A / B) % 9973 输入：数据的第第一行是一行T，表示有T组数据。每组数据有两个数n（0 <=n <=n + 9973）和 B（1 <=B <=10^9）。输出：对应

限时1000毫秒，内存65535MB。已知：n由A模9973计算，B与9973互质。计算A除以B再模9973。输入：T组数据，每组n和1亿以内的B。输出计算结果。

1000 ms |
内存限制： 65535

描述

已知：

1. n = (A % 9973);
2. gcd(B, 9973) = 1;

计算：

(A / B) % 9973

输入

数据的第一行是一个T，表示有T组数据.

每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9).

输出

对应每组数据输出(A / B) % 9973.

样例输入

2

1000 53

87 123456789

样例输出

7922

6060

#include <stdio.h>
const int MOD=9973;
typedef long long LL;

int extend_Eculid(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL r=extend_Eculid(b,a%b,y,x);
y-=a/b*x;
return r;
}
//模版而已 对于这道题 一定有解
LL solve(LL b,LL MOD)
{
LL x,y,res;
LL gcd=extend_Eculid(b,MOD,x,y);
if(1%gcd) return -1; //无解
if(MOD<0) MOD=-MOD;//如果MOD为负
x=x*1/gcd;
res=x%MOD;
if(res<0) res+=MOD;
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
LL n,b;
scanf("%lld %lld",&n,&b);
LL r=solve(b,MOD);
printf("%lld\n",(n*r)%MOD);
}
return 0;
}