Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：问ax+by=1的一组x>0的解，如果无解输出sorry.
思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。
然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。
x,y的通解为：**(x+kgx , y-kgy ） 其中：gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 **
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :Wed 12 Oct 2016 07:30:20 PM CST
4File Name :code/hdu/2669.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31int a,b;
32int exgcd( int a,int b,int &x,int &y)
33{
34 if (b==0)
35 {
36 x = 1;
37 y = 0;
38 return a;
39 }
40 int ret = exgcd(b,a%b,x,y);
41 int tmp = x;
42 x = y;
43 y = tmp - a/b*y;
44 return ret;
45}
46int main()
47{
48 #ifndef ONLINE_JUDGE
49 freopen("code/in.txt","r",stdin);
50 #endif
51 while (~scanf("%d%d",&a,&b))
52 {
53 int x,y;
54 if (exgcd(a,b,x,y)==1)
55 {
56 while (x<0)
57 {
58 x += b;
59 y -= a;
60 }
61 printf("%d %d\n",x,y);
62 }
63 else
64 {
65 puts("sorry");
66 }
67 }
68 #ifndef ONLINE_JUDGE
69 fclose(stdin);
70 #endif
71 return 0;
72}