首页 > 代码库 > Modified LCS

Modified LCS

2024-07-13 03:11:37   227人阅读

题目链接

  • 题意：
    给两个等差数列的长度，起点和数列的增加值，求两个数列中有几个数相同
  • 分析：
    将等差数列的通项公式化简后可以得到扩展欧几里得的结构，直接计算即可
  • 反思：
    求出方程的一个解后，得到的是下标。此时如果继续用下标判断会比较麻烦，因为同一个数在两个序列中的下标是不一样的，所以需要两个数列的下标范围均需要判断是否合法。而如果采用值判断，因为两个数列的满足题意的值是相同的，所以直接采用值判断会简单很多
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d)
{
    if (!b)
        x = 1, y = 0, d = a;
    else
    {
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}

int main()
{
    //freopen("0.txt", "r", stdin);
    int T;
    RI(T);
    FE(kase, 1, T)
    {
        LL n1, n2, f1, f2, d1, d2;
        LL a, b, v, x, y, dx, dy, gcd;
        cin >> n1 >> f1 >> d1 >> n2 >> f2 >> d2;
        a = d1, b = -d2, v = d1 - d2 + f2 - f1;
        ex_gcd(a, b, x, y, gcd);
        if (v % gcd != 0)
            puts("0");
        else
        {
            x *= v / gcd;
            x = f1 + (x - 1) * d1;
            dx = b / gcd * d1;
            x = ((x - 1) % dx + dx) % dx + 1;
            y = min(f1 + (n1 - 1) * d1, f2 + (n2 - 1) * d2);
            if (x <= y)
                cout << (y - x) / dx + 1 << endl;
            else
                puts("0");
        }
    }
    return 0;
}


Modified LCS


联系
我们