首页 > 代码库 > CSU 1446 Modified LCS 扩展欧几里得
CSU 1446 Modified LCS 扩展欧几里得
要死了，这个题竟然做了两天……各种奇葩的错误……
HNU的12831也是这个题。
题意：
给你两个等差数列，求这两个数列的公共元素的数量。
每个数列按照以下格式给出： N F D（分别表示每个数列的长度，首项，公差）。
思路：
先用扩展欧几里得得到两个数列的一个交点，然后求出两个数列的第一个交点。然后分别得到从第一个交点，到末项的可能交点数量。
假设 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) 时 才存在交点。
并且由此可以求得某一个交点。 然后就是求第一个交点，这个我跪了两天，不想说了 0 0
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <time.h>15 16 using namespace std;17 18 typedef long long ll;19 20 const int INF = 1<<30;21 22 ll N1, F1, D1, N2, F2, D2;23 24 ll exgcd(ll a, ll b, ll &x, ll &y) {25 if (b==0) {26 x = 1; y = 0;27 return a;28 }29 ll res = exgcd(b, a%b, y, x);30 y -= x*(a/b);31 return res;32 }33 34 ll myAbs(ll x) {35 return x>0 ? x : -x;36 }37 38 void input() {39 scanf("%lld%lld%lld%lld%lld%lld", &N1, &F1, &D1, &N2, &F2, &D2);40 }41 42 void solve() {43 ll x, y;44 ll d = exgcd(D1, D2, x, y);45 if (0!=(myAbs(F1-F2)%d)) {46 puts("0");47 return ;48 }49 ll k = (F1-F2)/d;50 ll k1 = -k*x, k2 = k*y;51 52 ll gg = max(F1, F2); //第一个交点必然大于等于两个起点53 ll lcm = D1/d*D2;54 55 gg = ((F1+k1*D1-gg)%lcm + lcm)%lcm + gg; //求出第一个·交点56 57 ll f1 = (gg-F1)/D1 + 1; //计算出第一个交点分别在两个数列中的下标58 ll f2 = (gg-F2)/D2 + 1;59 60 ll n1 = (N1-f1+(D2/d))/(D2/d);61 ll n2 = (N2-f2+(D1/d))/(D1/d);62 ll ans = min(n1, n2);63 if (ans<0) ans = 0;64 printf("%lld\n", ans);65 }66 67 int main() {68 #ifdef Phantom0169 freopen("HNU12831.txt", "r", stdin);70 #endif //Phantom0171 72 int Case;73 scanf("%d", &Case);74 while (Case--) {75 input();76 solve();77 }78 79 return 0;80 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。