hdu1576(扩展欧几里得求逆元板子）

要求(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

2 1000 53 87 123456789

 

Sample Output

7922 6060

分析：

直接求出B的逆元，改成(A*b)%9973结果即可

运用exgcd求即可，代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long exgcd(long long a, long long b, long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    long long r=exgcd(b,a%b,x,y);
    long long t=x;
    x=y;
    y=t-(a/b)*x;
    return r;
}
long long inverse(long long a,long long n)//注意要把逆元换到范围在0~MOD之间
{
    long long x,y,r;
    r=exgcd(a,n,x,y);
    return r==1?(x+n)%n:-1;
}
int main()
{
int n;
scanf("%d
",&n);
while(n--)
    {
    long long  a,b,x,k;
    scanf("%lld %lld",&a,&b);
    long long result=inverse(b,9973);
    printf("%lld
",a*result%9973);
     }
return 0;
}