AB HDU 1576
扩展欧几里得
题目描述：因为A值太大没有给出，给出了A%9973的值为n，另外还给出了B，求（A/B）%9973的值。
题目分析：
推一下方程，用扩展欧几里得算法。另（A/B）%9973的值为x, 方程推导过程：
（A/B）%9973=x -> A/B=9973*m+x -> A = 9973*m*B+x*B -> 将上式A带入A%9973 -> (9973*m*B+x*B)%9973 =n -> Bx%9973=n
Bx+9973y=n; 因为gcd(B,9973) =1，所以最后乘以n。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL m=9973;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL ans=exgcd(b,a%b,x,y);
LL t=y;
y=x-(a/b)*y;
x=t;
return ans;
}
int main()
{
int kase;
scanf("%d",&kase);
while(kase--)
{
LL B,n,x,y;
scanf("%lld %lld",&n,&B);
LL g=exgcd(B,m,x,y);
x*=n;
x=(x%m+m)%m;
cout << x << endl;
}
return 0;
}
