Hdu 1576 A/B 扩展欧几里得-白红宇

Hdu 1576 A/B 扩展欧几里得

阅读量：3904 次

发布时间：2019-05-23

本文共 960 字，大约阅读时间需要 3 分钟。

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

1000 53

87 123456789

Sample Output

7922

6060

设结果为k,则k=(A/B)%9973;

A/B=9973m+k;

A=B*k+9973*m*B;

因为:A%9973=n

所以:

n=（B*k+9973*m*B）%9973；

n%9973=k*B%9973.

k*B+9973y=n;

然后下面就是扩展欧几里得...

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;const long long  Mod=9973;int t;ll n,b;void Extend (ll A,ll B, ll& X,ll& Y){    if(B==0)    {        X=1; Y=0;        return;    }    else    {        ll ans,temp;        Extend(B,A%B,X,Y);        temp=X;        X=Y;        Y=temp-A/B*Y;    }}int main(){    scanf("%d",&t);    while (t--)    {        scanf("%lld%lld",&n,&b);        ll x,y;        Extend(b,Mod,x,y);        x=x*n;        x=(x%Mod+Mod)%Mod;        printf("%lld\n",x);    }    return 0;}