数学--数论--HDU1576 A / B(逆元）

问题描述

要求（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;

}

巴特西

数学--数论--HDU1576 A / B(逆元）

最新文章

热门文章