题目链接: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)); } }