uva 10673（扩展欧几里德）

题意：

對任何2個整數 x 和 k，存在另2個整數 p 和 q 使得：

要證明上面的式子是一件相當容易的事，所以我們不會要求你去做。我們要你做的事甚至更容易一些。給你 x 和 k 的值，請你找出 p 和 q 使得上面的式子成立。

思路：显然使用扩展欧几里德就可以直接解决。

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-03-26 22:53
 5  * Filename     : uva_10673.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 
34 ll exgcd(ll a, ll b, ll &x, ll &y){
35     ll t, m;
36     if(!b && !a) return -1;
37     if(!b) x = 1, y = 0;
38     else {
39         m = exgcd(b, a%b, x, y);
40         t = x, x = y, y = t - (a/b)*y;
41     }
42     return m;
43 }
44 
45 int main()
46 {
47 //    freopen("in.txt", "r", stdin);
48 
49     int T;
50     cin >> T;
51     while(T--){
52         double a, b;
53         cin >> a >> b;
54         ll c = (ll)floor(a/b), d = (ll)ceil(a/b);
55         ll x, y;
56         exgcd(c, d, x, y);
57         ll oa = x*(a/__gcd(c, d)), ob = y*(a/__gcd(c, d));
58         cout << oa << ' ' << ob << endl;
59     }
60     return 0;
61 }

View Code