本文共 939 字，大约阅读时间需要 3 分钟。
题目链接： http://codeforces.com/problemset/problem/787/A
题目描述： 问等差数列c1 + a*x(a 为 常数)， c2 + b*y(b 为 常数) 能不能有一项是相等的
解题思路： a*x + c1 = b*y + c2, a*x + b*(-y) = c2 - c1 = c， 所以问题等价于是否存在正整数使得等式成立， 扩欧
代码：
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;void exgcd( int a, int b, int &g, int &x, int &y ) { if( !b ) { x = 1, y = 0, g = a; } else { exgcd(b, a%b, g, y, x); y -= a / b * x; }}int main() { int a, c1, b, c2; cin >> a >> c1 >> b >> c2; int c = c2 - c1; int g, x, y; exgcd(a, b, g, x, y); if( c % g ) { cout << -1 << endl; } else { int b1 = b / g; x *= (c/g); x = (x%b1+b1)%b1; while( (c-a*x)/b > 0 ) x += b1; cout << a * x + c1 << endl; } return 0;}
思考： 自己对扩欧的理解还是不够深刻
转载于:https://www.cnblogs.com/FriskyPuppy/p/7625198.html
