Problem J. Modified LCS【扩展欧几里得】

题意

• 给两个等差数列的长度，起点和数列的添加值，求两个数列中有几个数相同

题解

• 将等差数列的通项公式化简后能够得到扩展欧几里得的结构，直接计算就可以
• 假设 $F1+K1?D1=F2+K2?D2$ 是某一个交点， 移向得到 $F1?F2=K2?D2?K1?D1$。 由扩展欧几里得定理的结论 $x?a+y?b=K?gcd(a,b)。$
  所以 只有 $F1?F2=K?gcd(D1,D2)$ 时 才存在交点。

AC-Code

#include <bits/stdc++.h>
using namespace std;ll exgcd(ll a, ll b, ll& x, ll& y)//扩展欧几里得算法
{
    if (b == 0) {
    x = 1; y = 0;return a;  //到达递归边界开始向上一层返回}ll r = exgcd(b, a % b, x, y);ll temp = y;    //把x y变成上一层的y = x - (a / b) * y;x = temp;return r;     //得到a b的最大公因数
}int main() {
    int T;	cin >> T;while (T--) {
    ll n1, f1, d1, n2, f2, d2;	cin >> n1 >> f1 >> d1 >> n2 >> f2 >> d2;ll f = f2 - f1;ll x0, y0, gcd_ = exgcd(d1, -d2, x0, y0);if (f % gcd_) {
    cout << 0 << endl;  continue;}ll r = abs((-d2) / gcd_);ll x = (x0 * f / gcd_ % r + r) % r;ll y = (f - x * d1) / (-d2);ll dx = abs(d1 / gcd_);ll dy = abs(d2 / gcd_);ll ans = min((n1 - x - 1) / dy, (n2 - y - 1) / dx) + 1;cout << ans << endl;}return 0;
}