问题描述 要求(A / B)%9973,但由于A很大,我们只被告知n(n = A%9973)(我们给定的A必能被B整除,且gcd(B,9973)= 1)。
输入项 数据的第一行是一个T,表示有T组数据。 每组数据有两个数n(0 <= n <9973)和B(1 <= B <= 10 ^ 9)。
输出量 对应每组数据输出(A / B)%9973。
样本输入 2 1000 53 87 123456789
样本输出 7922 6060
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long INT;
const INT p = 9973;
INT ex_gcd(INT a, INT b,INT &x, INT &y)
{
if(b == 0){
x = 1;
y = 0;
return a;
}
INT d = ex_gcd(b , a % b,x,y);
INT tmp =x;
x = y;
y = tmp - a / b * y;
return d;
}
int main()
{
int T;
cin >> T;
while(T --){
INT n, b,x,y;
cin >> n >> b;
ex_gcd(b, p,x,y);
cout << (x % p * n % p + p) % p << endl;
}
return 0;
}