You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
|
// https://vjudge.csgrandeur.cn/problem/HDU-1576
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
/*
|
|
|
|
|
|
测试用例
|
|
|
|
|
|
2
|
|
|
|
|
|
1000 53
|
|
|
|
|
|
87 123456789
|
|
|
|
|
|
|
|
|
|
|
|
答案
|
|
|
|
|
|
7922
|
|
|
|
|
|
6060
|
|
|
|
|
|
*/
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int MOD = 9973;
|
|
|
|
|
|
|
|
|
|
|
|
LL exgcd(LL a, LL b, LL &x, LL &y) {
|
|
|
|
|
|
if (!b) {
|
|
|
|
|
|
x = 1, y = 0;
|
|
|
|
|
|
return a;
|
|
|
|
|
|
}
|
|
|
|
|
|
LL d = exgcd(b, a % b, y, x);
|
|
|
|
|
|
y -= a / b * x;
|
|
|
|
|
|
return d;
|
|
|
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int t;
|
|
|
|
|
|
cin >> t;
|
|
|
|
|
|
while (t--) {
|
|
|
|
|
|
LL x, y;
|
|
|
|
|
|
LL a, b;
|
|
|
|
|
|
cin >> a >> b;
|
|
|
|
|
|
exgcd(b, MOD, x, y);
|
|
|
|
|
|
x = (x % MOD + MOD) % MOD; //对比使用费马小定理，这里对于扩展欧几里得算出的逆元，还需要进一步模一下 MOD才行，否则可能是负的
|
|
|
|
|
|
cout << (x * a) % MOD << endl;
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
