[关闭]
@xunuo 2017-02-27T19:47:05.000000Z 字数 987 阅读 1029

HDU 1576 A除以B(拓展欧几里得)


Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

数论


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=A%9973 ==> n=A-A/9973*9973
又∵A/B=x ==> A=Bx
∴Bx-A/9973*9973=n
==> Bx-9973y=n
∵gcd(B,9973)=BX1+9973Y1=1;即可求出X1
等式两边同乘以n
故 B(nX1)-9973(-nY1)=n
可知nX1就是BX-9973Y=n的解
∴x=nx1
为避免负数出现答案应该为(x%9973+9973)%9973

代码:

  1. void e_gcd(int a,int b,int &x,int &y)
  2. {
  3. int t;
  4. if(b==0)
  5. {
  6. x=1;
  7. y=0;
  8. return;
  9. }
  10. else
  11. {
  12. e_gcd(b,a%b,x,y);
  13. t=x;
  14. x=y;
  15. y=t-(a/b)*y;
  16. }
  17. }
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<algorithm>
  5. using namespace std;
  6. #define ll long long
  7. #define mod 9973
  8. void e_gcd(int a,int b,int &x,int &y)
  9. {
  10. int t;
  11. if(b==0)
  12. {
  13. x=1;
  14. y=0;
  15. return;
  16. }
  17. else
  18. {
  19. e_gcd(b,a%b,x,y);
  20. t=x;
  21. x=y;
  22. y=t-(a/b)*y;
  23. }
  24. }
  25. int main()
  26. {
  27. int t;
  28. scanf("%d",&t);
  29. while(t--)
  30. {
  31. int n,b,x,y,ans;
  32. scanf("%d%d",&n,&b);
  33. e_gcd(b,mod,x,y);
  34. x*=n;
  35. ans=(x%mod+mod)%mod;
  36. printf("%d\n",ans);
  37. }
  38. return 0;
  39. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注