题目描述：
Problem Description
Problem Description
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2 1000 53 87 123456789
Sample Output
7922 6060
题目思路：
看完题目会容易想到扩展欧几里德，当然前提是你知道扩展欧几里德算法，扩展欧几里德算法用来求解已知a和b求解x和y的方程，并且这么方程满足贝祖等式 ax + by = gcd(a,b)。通过求出的贝祖等式的解，就可以求出ax + by = c的通解。说了半天跟这道题有什么关系呢，在这道题目中给定了n和B，并且告诉了gcd(B,9973) = 1, 让我们求解(a/b)%9973。那么我们就要想办法凑出Bx + 9973y = c 这样的方程式，
因为 n = A%9973 所以 A - A/9973 * 9973 = n ①
假设A/B = x 所以A = Bx ②
假设A/9973 = y 所以A / 9973 * 9973 = 9973y ③
将②和③带入① 得到 Bx + (-9973y) = n
这样我们就可以通过扩展欧几里德求出 x 了，注意 x 代表的是 A/B 所以在输出答案的时候要对 x 进行取模，并确保 x 不是负数。
题目代码：
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
/*
Bx + (-9973y) = n
*/
void exgcd(LL a, LL b, LL &x, LL &y){if(!b){x = 1; y = 0; return; }else{exgcd(b, a%b, y, x); y -= (a/b)*x;}
}
int t;
LL a, b, x, y, n;
int main(){
// freopen("input.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%lld %lld", &n,&a);b = 9973;exgcd(a,b,x,y);x *= n;x = (x%9973+9973)%9973;printf("%lld\n",x);}return 0;
}