nyoj1235 A/B Problem(扩展欧几里德求逆元)

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;
}