寒假训练5I

寒假训练5I

要求(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)。
Output
对应每组数据输出(A/B)%9973。
题目分析：该题用扩展欧几里得算法较容易得出，具体分析暂略。
AC代码：

#include<iostream>
using namespace std;
int p(int a,int b,int &x,int &y)
{if(b==0)
{x = 1;y = 0; return a;
}int d = p(b, a%b, x, y);
int k = x;
x = y;
y = k - a / b * y;
return d;
}
int main()
{int n, B,t,x,y,i,j;cin >> t;while(t--){cin >> n >> B;i = p(B, 9973, x, y);j = x * n;i = (j % 9973 + 9973) % 9973;cout << i << endl;}
}