HDU 1576 A/B 暴力也能过。扩展欧几里得

A/B

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

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

 1 /*
 2 a/b=x;
 3 a=bx;
 4 a%9973=n;
 5 a-a/9973*9973=n;
 6 bx-a/9973*9973=n;
 7 
 8 ax+by=c;
 9 ==>
10 a=b;
11 b=9973;
12 c=n;
13 
14 */
15 
16 
17 
18 #include<stdio.h>
19 
20 
21 __int64 Ex_GCD(__int64 a,__int64 b,__int64 &x,__int64 &y)
22 {
23     if(b==0)
24     {
25         x=1;
26         y=0;
27         return a;
28     }
29     __int64 g=Ex_GCD(b,a%b,x,y);
30     __int64 hxl;
31     hxl=x-(a/b)*y;
32     x=y;
33     y=hxl;
34     return g;
35 }
36 
37 int main()
38 {
39     __int64 T,n,a,b,c,k,x,y;
40     while(scanf("%I64d",&T)>0)
41     {
42         while(T--)
43         {
44             scanf("%I64d%I64d",&n,&b);
45             a=b;
46             c=n;
47             b=9973;
48             k=Ex_GCD(a,b,x,y);
49             x=x*(c/k);
50             b=b/k;
51             x=x%(b);
52             while(x<0)
53             {
54                 x=x+b;
55             }
56             printf("%I64d
",x);
57         }
58     }
59     return 0;
60 }