hdu1576 A/B(扩展的欧几里德算法)

本文主要是介绍hdu1576 A/B(扩展的欧几里德算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A/B

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1369 Accepted Submission(s): 1045

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

2 1000 53 87 123456789 

Sample Output

7922 6060 

 题解： 

 因为：题目已知n和B，又知gcd(B,9973) = 1, 

 且n=A%9973，需要求(A/B)%9973， 

 由于不知道A,所以需要把A替换掉， 

 所以设 

              ans=(A/B)%9973             ……                                             (1) 

 (1)式中    存在x使得 

                A/B=9973x+ans,               ……                                         (2) 

 (2)  式中两边同时乘上B,得 

                A=9973*B*x+ans*B      ……                                             (3) 

又因n=A%9973,

一定存在y使得

n=A-9973*y …… (4)

把(3)代入(4)得

n=9973*B*x+ans*B -9973*y

合并得

n=ans*B +(B*x-y)9973 …… (5)

又有 gcd(B,9973) = 1，所以(5)式两边同时除以n,得

1=ans/n*B+(B*x-y)/n*9973

就可以看成ax+by=1的形式，

运用扩展的欧几里德算法求出ans/n,

此时a=B,b=9973,x=ans/n;

所以套用扩展的欧几里德算法模版求出x,然后再乘上n,即可得出结果ans=(A/B)%9973；

代码实现：

#include<iostream>
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的xx*=n;   //此时的x为 n=ans*B +(B*x-y)9973 中的解ans了tmp=(x%MOD+MOD)%MOD;   //防止x为负，有题意x必为正数cout<<tmp<<endl;}return 0;
}