[HDU1576] A/B（扩展欧几里得）

传送门

n = A % 9973 -> n = A - A / 9973 * 9973

设 x = A / B（题目所述，B|A） -> A = B * x

所以 B * x - A / 9973 * 9973 = n

设 y = A / 9973

则 B * x - 9973 * y = n

B 和 n 已知， gcd(B, 9973) == 1

所以可以求出 B * ｘ + 9973 *(- y) == 1 时的 x 的解

然后 x 再 * n，最后求 (x % 9973 + 9973) % 9973 即为答案

——代码

#include <cstdio>

inline void exgcd(int a, int b, int &x, int &y)
{
    if(!b){x = 1, y = 0; return;}
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

int main()
{
    int n, b, x, y, T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &b);
        exgcd(b, 9973, x, y);
        x *= n;
        printf("%d
", (x % 9973 + 9973) % 9973);
    }
    return 0;
}