HDU 1576拡張ユークリッド

A/B
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4627 Accepted Submission(s): 3610
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<=10^9)の2つの数がある.
Outputは、各データ出力(A/B)%9973のセットに対応する.
Sample Input 2 1000 53 87 123456789
Sample Output 7922 6060
Author xhd
Source HDU 2007-1 Programming Contest
(A/B)%9973=K+9973 X=A/B KB+9973 XB=AだからA%9973=N(KB+9973 XB)%9973=N KB%9973=N KB=9973 Y+N KB-9973 Y=N KB/N-9973 Y/N=1=GCD(9973,B)セットユークリッドテンプレートで良い

#include
using namespace std;
const int MOD = 9973;
void extendGcd(int a, int b, int &x, int &y) //  gcd，    gcd(a,b)  ax+by=gcd(a,b) x,y  
        {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    } else {
        extendGcd(b, a % b, x, y);
        int tmp = x;
        x = y;
        y = tmp - a / b * y;
    }
}
int main() {
    int t, n, b, x, y, tmp;
    cin >> t;
    while (t--) {
        cin >> n >> b;
        extendGcd(b, MOD, x, y);  //  bx+9973y=1 x
        x *= n;   //   x bx1-9973y1=n   x1 
        tmp = (x % MOD + MOD) % MOD;   //  x  ，   x    
        cout << tmp << endl;
    }
    return 0;
}