本文主要是介绍CSU - 1446 Modified LCS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Input
Output
Sample Input
3 5 3 4 15 3 1 10 2 2 7 3 3 100 1 1 100 1 2
Sample Output
4 3 50
题意：求两个等差序列相同的元素个数
思路： 首先我们可以假设得到解是当 F1 + D1 * K1 = F2 + D2 * K2，那么我们可以通过扩展欧几里德算法来求出最小的正数解，再来是当我们知道一组解是（x0, y0）的时候，任意解都可以是(x0 + kb', y0-ka') {b' = b/gcd, a' = a/gcd}，在各自的范围内求解，注意处理范围里有多少解的时候最好模拟一下，容易理解
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;ll x, y, g;void exgcd(ll a, ll b) {if (b == 0) {x = 1;y = 0;g = a;return;}exgcd(b, a%b);ll t = x;x = y;y = t - a / b * y;return;
}int main() {int t;ll n1, n2, f1, f2, d1, d2;scanf("%d", &t);while (t--) {cin >> n1 >> f1 >> d1 >> n2 >> f2 >> d2;ll f = f2 - f1;exgcd(d1, -d2);if (f % g) {printf("0\n");continue;}else {ll r = abs((-d2)/g);x = ((x * f / g) % r + r) % r;y = (f - x * d1) / (-d2);ll dx = abs(d1 / g);ll dy = abs(d2 / g);ll ans = min((n1 - 1 - x) / dy, (n2 - 1 - y) / dx) + 1;cout << ans << endl;}}return 0;
}
这篇关于CSU - 1446 Modified LCS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
