hdu 1576 A/B

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

　　简单exgcd应用。。。无压力1y。。。。

View Code

 1 /*
 2  * Author: SCAU_Lyon
 3  * Problem: hdu 1576
 4  * Method: ex-gcd
 5  */
 6 
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <cmath>
10 #include <algorithm>
11 #include <cassert>
12 
13 using namespace std;
14 typedef __int64 ll;
15 const int mod = 9973;
16 
17 void exgcd(int a, int b, ll &x, ll &y, int &d){
18     if (b){
19         exgcd(b, a % b, y, x, d);
20         y -= (a / b) *x;
21     }
22     else{
23         d = a;
24         x = 1;
25         y = 0;
26     }
27 }
28 
29 int main(){
30     int n, b, d;
31     int T;
32     ll x, y;
33 
34     scanf("%d", &T);
35     while (T-- && scanf("%d%d", &n, &b)){
36         exgcd(b, mod, x, y, d);
37         assert(d == 1);
38         x *= n;
39         x %= mod;
40         while (x < 0) x += mod;
41         printf("%I64d\n", x);
42     }
43 
44     return 0;
45 }

——written by Lyon