hdu 1576 A/B（拓展欧几里得）

A/B

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

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: 1788 1211 1787 1299 1573

解题思路：

（1）n=A%9973，则n=A-A/9973*9973。又A/B=x，则A=Bx。所以Bx-A/9973*9973=n。即Bx-9973y=n。

到这里我们可以发现：只要求出x的值，即可算出x%9973，也就是(A/B)%9973了。顺利解决了！ gcd（a，b） = ax + by;

（2）如何求出x呢？题目的输入是n和B，利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1，y1。

等式两边同乘以n，得B(nx1)-9973(-ny1)=n（nx1=x.-ny1=y).可知nx1就是Bx-9973y=n的解了！！！即x=nx1。

（3）对于（2）得到的x可能是负数，由题这显然是不正确的，如果是负数则加上9973再与n相乘后%9973即可得到正确结果。

 1 #include <iostream>  
 2 #include <cstdio>  
 3 #include <cstring>  
 4 #include <cmath>  
 5 #include <vector>  
 6 #include <string>  
 7 #include <queue>  
 8 #include <stack>  
 9 #include <algorithm>  
10 
11 #define INF 0x7fffffff  
12 #define EPS 1e-12  
13 #define MOD 1000000007  
14 #define PI 3.141592653579798  
15 #define N 100000  
16 
17 using namespace std;
18 
19 typedef long long LL;
20 
21 LL e_gcd(LL a, LL b, LL &x, LL &y)
22 {
23     LL d = a;
24     if (b != 0)
25     {
26         d = e_gcd(b, a%b, y, x);
27         y -= a / b * x;
28     }
29     else
30     {
31         x = 1; y = 0;
32     }
33     return d;
34 }
35 
36 LL cal(LL a, LL b, LL c)
37 {
38     LL x, y;
39     LL gcd = e_gcd(a, b, x, y);
40     if (c%gcd != 0) return -1;
41     x *= c / gcd;
42     b /= gcd;
43     if (b < 0) b = -b;
44     LL ans = x % b;
45     if (ans <= 0) ans += b;
46     return ans;
47 }
48 
49 int main()
50 {
51     LL n, b, t;
52     cin >> t;
53     while (t--)
54     {
55         scanf("%I64d%I64d", &n, &b);
56         LL ans = cal(b, 9973, n);
57         if (ans == -1) printf("Impossible
");
58         else printf("%lld
", ans);
59     }
60     return 0;
61 }