HOJ 1576 A/B（扩展欧几里得）

扩展欧几里得
本题要点：
1、推导：
const int m = 9973， n < m,
n = A % 9973, 也就是 n = A % m, 改写为 A = m * x + n
而 A 能 整除 B, 假设 A = B * y
联立以上两个式子， m * x + n = B * y
也就是解方程 -m * x + B * y = n。
解除 y （y = A / B）, 答案就是 y % m;
2、 方程 -m * x + B * y = n， 一定有解， 因为 gcd(B, n) == 1
最后求出来 y 可能是负数，输出 printf("%d\n", (m + y % m) % m);

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int m = 9973;
int T, A, B, n;int gcd(int a, int b)
{
    return b == 0? a : gcd(b, a % b);
}int exgcd(int a, int b, int& x, int& y)
{
    if(!b){
    x = 1, y = 0;return a;}int d = exgcd(b, a % b, x, y);int z = x; x = y; y = z - y * (a / b);return d;
}void solve()
{
    int a, b, x, y;a = -9973, b = B;exgcd(a, b, x, y);y *= n / gcd(a, b);printf("%d\n", (m + y % m) % m);
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d%d", &n, &B);	solve();}return 0;
}/* 2 1000 53 87 123456789 *//* 7922 6060 */