首页 > 代码库 > Modified LCS （扩展欧几里德）细写了对这个算法思路的理解

Modified LCS （扩展欧几里德）细写了对这个算法思路的理解

2024-07-05 13:31:58   229人阅读

题目：Modified LCS

为过此题去仔细研究了下扩展欧几里德算法，领悟了一些精华。

模板为：

void gcd(ll a, ll b, ll& d, ll& x, ll& y) 
{ 
    if(!b) {d = a; x = 1; y = 0;} 
    else{ gcd(b, a%b, d, y, x); y -= x*(a/b);} 
}
这里算出来的x,y是对于方程ax+by=gcd(a,b)而言的一组解。
为什么叫扩展欧几里德说明肯定用了欧几里德算法的原理即：gcd(a,b)=gcd(b,a%b);
ax+by=gcd(a,b)=gcd(b,a%b)=。。。可以一直使用欧几里德算法直到b=0,即就是刚才算法模板的第一句话，
if(!b) {d = a; x = 1; y = 0;}
当b=0时，a = gcd(a,b)，ax+by=gcd(a,b)这个方程就变为ax=a了，即x=1，y等于几其实是随便的，但是必须要有数字为了反推出之前的解，这里就为了简洁就等于0。PS：可以尝试不填0说不定靠点运气能提高效率（玩笑）。

然后得到了最后一组解（1，0）如何推出第一个方程的解呢？

显然可知：gcd(b,a%b) = bx+a%by。注意这里的 x和y跟第一个方程的x和y是不一样的。
连等式得：ax1 + by1 = bx2 + a%by2 = bx2 + (a - a/b*b)y2这里是利用取模的性质.即a%b = a - a/b*b。
交换位置得: ax1 + by1 = ay2 + b(x2 - a/b * y2);
因为是构造解所以根据恒等式设 x1=y2 ，y1 = (x2 - a/b * y2);
注意模板里第二句
else{ gcd(b, a%b, d, y, x); y -= x*(a/b);}

x和y是交换位置的。就是因为 x1=y2，即上一层的 y是当前的x，当前gcd的y应该是上一层的x减去a/b×y。就是y1 = (x2 - a/b * y2);
但是在这
gcd(b, a%b, d, y, x);
之后。你上一层的x的值变成了当前y的值，上一层y的值变成了当前x的值。当前的x值就是这个，但是y值却不是上一层的x，需要计算，所以就有了
 y -= x*(a/b);
如果还有不懂可以拿笔模拟一下，先不停的递归直到终点即b==0时，然后给x,y赋值1和0，再一步一步回推执行 y -= x*(a/b);


好了。可以讲那道题了。题意就是2个等差序列，告诉你个数，起点，公差，问你有几个数是2个序列共有的？

此题就是要解F1 + D1x = F2 + D2y在0=<x<=N1-1 && 0=<y<=N2-1最多的整数解。（F为起点，D为公差，N为个数）
移项可得 D1x - D2y = F2 - F1一个标准的可用扩展欧几里德的方程。
唯一不同的是方程b的地方要用-D2，先用模板解出一个解x0,y0。

先设g = gcd(d1,d2)即最小公约数。

明确下思路，此题是要求最小且大于等于0的x和y，然后这个2个点就是起点了，其后一样的数就是起点加上2个序列公差的最小公倍数×k了。最小公倍数为d1*d2/g。
第一个序列相同数的间隔为最小公倍数除以d1,即p1 = d1*d2/g/d1 = d2/g，同理第二个序列相同数的间隔为p2 = d1/g。
故第一个序列可能的相同数个数为(N1 - 1 - x)/p1,第二个为(N1 - 1 - y)/p2。
答案为2个值的较小者。

刚才说的间隔就可以用来求方程的其他解，即x = x0 + k*p1,y = y0 + k*p2。
还要分2种情况来求x,y。
其实是2个方向，如果x0,y0有一个小于0，说明k要大于0，一直分别加p1,p2直到2者都大于等于0为止。
如果都大于0，则说明可能太大了，要求最小且大于等于0的x和y嘛，说明k要小于0。然后一直分别减p1,p2直到2者不能再减了，再减就有一项小于0为止。
具体思路已经非常清晰了，如果没有看懂希望多看几遍应该就能想通。

AC代码：
#include<cstdio> 
#include<ctype.h> 
#include<algorithm> 
#include<iostream> 
#include<cstring> 
#include<vector> 
#include<stack> 
#include<cmath> 
#include<queue> 
#include<set> 
#include<ctime> 
using namespace std; 
#define ll long long 
  
void gcd(ll a, ll b, ll& d, ll& x, ll& y) 
{ 
    if(!b) {d = a; x = 1; y = 0;} 
    else{ gcd(b, a%b, d, y, x); y -= x*(a/b);} 
} 
  
int main() 
{ 
    ll n1,f1,d1,n2,f2,d2; 
    int t; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2); 
        ll x,y,g; 
        gcd(d1,-d2,g,x,y); 
        ll f = f2-f1; 
        x *= f/g;//小心溢出 
        y *= f/g; 
        g = abs(g); 
        ll a = d1/g; 
        ll b = d2/g; 
        if(x < 0 || y < 0) 
        { 
            while(x < 0 || y < 0) 
            { 
                x += b; 
                y += a; 
            } 
        } 
        else
        { 
            while(x >= 0 && y >= 0) 
            { 
                x -= b; 
                y -= a; 
            } 
            x += b; 
            y += a; 
        } 
        ll num1 = (n1-1-x)/b; 
        ll num2 = (n2-1-y)/a; 
        printf("%lld\n",min(num1,num2)+1); 
    } 
    return 0; 
} 
  
/************************************************************** 
    Problem: 1446 
    User: HNU_TEAM_3 
    Language: C++ 
    Result: Accepted 
    Time:0 ms 
    Memory:1484 kb 
****************************************************************/


联系
我们