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

 

Output

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

 

Sample Input

 

Sample Output

 

Author

xhd

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

typedef long long LL;

/*

要求(A/B)%9973

ax+by = c

a*x = c%b 在这里b=9973,

9973*x+B*y = A

B*y = A%9973 在这里求最小的B就是答案
按照求逆元的方法

*/

LL ex_gcd(LL a,LL b,LL &x,LL &y)

{

    if(b==)

    {

        x = ;

        y = ;

        return a;

    }

    LL ans = ex_gcd(b,a%b,x,y);

    LL tmp = x;

    x = y;

    y = tmp - a/b*x;

    return ans;

}

LL cal(LL a,LL b,LL c)

{

    LL x=,y=;

    LL gcd = ex_gcd(a,b,x,y);

    if(c%gcd!=) return -;

    x *= c/gcd;

    b /= gcd;

    if(b<) b = -b;

    LL ans = x%b;

    if(ans<) ans += b;

    return ans;

}

int main()

{

    LL t,n,b;

    scanf("%lld",&t);

    while(t--)

    {

        scanf("%lld%lld",&n,&b);

        printf("%lld\n",cal(b,,n));

    }

}