HDU|HDU 1576 A/B（拓展欧几里得，模板题） GCD|LCM|拓展欧几里得|小有趣的

http://acm.hdu.edu.cn/showproblem.php?pid=1576

A/B Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4451Accepted Submission(s): 3448

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
Author xhd
Source HDU 2007-1 Programming Contest
Recommend linle|We have carefully selected several similar problems for you:17881211129915731452

思路：
【HDU|HDU 1576 A/B（拓展欧几里得，模板题）】基础的拓展欧几里得，
这里是升级版>>>>>青蛙的约会

Code：

#include typedef __int64 LL; LL ExpandGcd(LL a,LL b,LL &x,LL &y) { //拓展欧几里得 if(b==0) { x=1,y=0; return a; } LL ans=ExpandGcd(b,a%b,x,y),temp=x; x=y; y=temp-a/b*y; return ans; }LL Inver(LL a,LL b,LL c) {//数 a 对于数 b 的乘法逆元: //满足方程a*x = c (mod b)的 x LL x,y; LL gcd=ExpandGcd(a,b,x,y); if(c%gcd!=0)return -1; x=x*c/gcd; b=b/gcd; if(b<0)b=-b; LL ans=x%b; if(ans<=0) ans+=b; return ans; }int main() { int t; scanf("%d",&t); while(t--) { LL n,B; scanf("%I64d %I64d",&n,&B); LL ans=Inver(B,9973,n); printf("%I64d\n",ans); } return 0; }