A/B

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

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 <= 109)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

2
1000 53
87 123456789

Sample Output

7922
6060

思路：

有题目可知(A / B) % 9973 = x，这时x就是最终要求出来的值了，
(A / B) - k * 9973 = x;
A = x * B + k * 9973 * B， n = A % 9973;
n = (x * B + k * 9973 * B) % 9973;
n = x * B % 9973;
x * B + y * 9973 = n；
所以将B看作a，9973看作b, 就有了ax+by=c，最后的gcd = 1(题目说的)所以当求出x之后乘c在取余就行了。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 9973;
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return ;
    }
    Exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
}
int main() {
    ll n, b, t;
    scanf("%lld", &t);
    while (t--) {
        ll x, y;
        scanf("%lld %lld", &n, &b);
        Exgcd(b, mod, x, y);
        x *= n;
        x = (x % mod + mod) % mod;
        printf("%lld\n", x);
    }
    return 0;
}