首页 > 代码库 > POJ 1061 青蛙的约会（扩展欧几里得算法）
POJ 1061 青蛙的约会（扩展欧几里得算法）
http://poj.org/problem?id=1061
思路：
搞懂这个扩展欧几里得算法花了不少时间，数论真的是难啊。
含义：找出一对整数，使得ax+by=gcd（a，b）。
接下来看这道题目，（x+mt）-（y+nt）=kl，转换成（n-m）t+kl=x-y。
令a=n-m，b=l，c=x-y，那么上式就变成了at+kb=c，之后就参照上面的算法来计算就行，具体参见代码。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 8 long long int x, y, m, n, l; 9 10 long long gcd(long long a, long long b)11 {12 return b == 0 ? a : gcd(b, a%b);13 }14 15 void extend_gcd(long long a, long long b, long long& x, long long& y)16 {17 if (b == 0)18 {19 x = 1;20 y = 0;21 return;22 }23 else24 {25 extend_gcd(b, a%b, x, y);26 long long int temp = x;27 x = y;28 y = temp - a / b*y;29 }30 }31 32 int main()33 {34 //freopen("D:\\txt.txt", "r", stdin);35 while (cin >> x >> y >> m >> n >> l)36 {37 long long int a = n - m, b = l, c = x - y, p, q;38 long long int d = gcd(a, b);39 //如果c不能被d整除，肯定没有整数解40 if (c%d)41 {42 cout << "Impossible" << endl;43 continue;44 }45 extend_gcd(a, b, p, q);46 p = p*c / d;47 p = p%l;48 if (p < 0) p += l;49 cout << p << endl;50 }51 return 0;52 }
POJ 1061 青蛙的约会（扩展欧几里得算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。