题目链接：https://www.jisuanke.com/contest/11486/676873
题目描述：
有两个等差数列A,B,给定长度N,起始点F,等差D,LCS的长度。
解题笔记：
这题就是个拓展欧几里得，A的某一位和B的某一位相等，则有：
-> F1+D1x=F2+D2y
-> D1x-D2y=F2-F1
于是问题便转化为了拓展欧几里得求符合条件解的个数。
看起来模板以上就解决了吧，于是我写了如下代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll d = exgcd(b, a%b, y, x);
    y = y - a/b * x;
    return d;
}
ll gcd(ll a, ll b)
{
    return b ? gcd(b,a%b) : a;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        ll n1,f1,d1,n2,f2,d2, x, y;
        scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
        ll m = gcd(d1, d2);
        if(abs(f1-f2) % m != 0) {
            printf("0\n");
            continue;
        }
        exgcd(d1, d2, x, y);
        ll ans = 0;
        x *= (f2-f1)/m;
        y *= (f2-f1)/m;
        ll b1 = d2/m;
        ll a1 = d1/m;
        if(x < 0)
        {
            while(x < 0) x+=b1,y-=a1;
            for(int i = x; i < n1; i+=b1,y-=a1)
                if(-y >= 0 && -y < n2) ans++;
        }
        else if(x >= n1)
        {
            while(x >= n1) x-=b1, y+=a1;
            for(int i = x; i >= 0; i-=b1,y+=a1)
                if(-y >= 0 && -y < n2) ans++;
        }
        else
        {
            int ty = y;
            for(int i = x; i < n1; i+=b1, ty-=a1)
            if(-ty >= 0 && -ty < n2) ans++;
            ty = y+a1;
            for(int i = x-b1; i >= 0; i-=b1,ty+=a1)
            if(-ty>=0 && -ty<n2) ans++;
        }
        printf("%lld\n",ans);
    }
}

在后面这个求全部解这里一个一个求得话时间复杂度是O(n)。
但其实并不需要这样。
如果我们求出一组非负解(x0,y0),那么完全可以在O(1)的复杂度求出x0<=x<=n1的解的个数，因为x是一个以x0为初项的等差数列啊。
怎么求非负解(x0,y0) ？ 先用exgcd求出x0，y0，然后x=x0+b/m，y=((a,b)-ax)/b,不断往上加就行了。
*代码：**

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll d = exgcd(b, a%b, y, x);
    y = y - a/b * x;
    return d;
}
pair<pair<ll,ll>, pair<ll,ll> > cal(ll a, ll b, ll c)
{
    ll x, y;
    ll d = exgcd(a, b, x, y);
    if(c % d) return make_pair(make_pair(-1,-1),make_pair(-1,-1));
    x *= c/d;
    ll t = b / d; if(t < 0) t = -t;
    x = (x % t + t) % t;         //这个取模用的很好，值得注意
    y = (c - a*x) / b;
    while(y < 0)
    {
        x += t;
        y = (c - a*x) / b;        //因为b是负的，x和y可以都增加 
    }
    return make_pair(make_pair(x, t), make_pair(y, a/d < 0 ? -a/d : a/d));
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n1,f1,d1,n2,f2,d2;
        scanf("%lld%lld%lld%lld%lld%lld",&n1,&f1,&d1,&n2,&f2,&d2);
        auto p = cal(d1,-d2,f2-f1);
        ll x0 = p.first.first, dx = p.first.second;
        ll y0 = p.second.first, dy = p.second.second;
        if(x0 == -1 && y0 == -1 && dx == -1 && dy == -1){
            printf("0\n"); continue;
        } 
        ll cx = (n1-1-x0)/dx + 1;
        ll cy = (n2-1-y0)/dy + 1;
        printf("%lld\n",min(cx,cy));
    }
}