题解：P11846 [USACO25FEB] Transforming Pairs P

· · 题解

Solution

简单模拟题。

先考虑 a,b \ge 0 的情况（显然 a,b \le 0 可以转化过来）。发现过程中一定有 a' \ge 0、b' \ge 0 恒成立。如果出现 c<0 或 d<0 无解。

所以如果我们知道了 (c,d)，往前推一步，要么是 (c-d,d)，要么是 (c,d-c)。显然如果 c \neq d，肯定是大的减去小的。而如果 c=d，则 (c,0) 和 (0,c) 都可以作为上一步。

所以我们直接模拟辗转相除即可。最小步数存在且唯一。

接下来考虑 a>0、b<0 的情况。（因为 a 和 b 高度对称，所以可以大量化归。）

如果 c<0 且 d>0，显然不可能成功了。

否则，如果 c \ge 0 且 d \le 0，不妨设 a' = a、b' = -b，则 (a,b) \to (a+b,b) 可以改写为 (a,-b') \to (a-b',-b')。所以我们可以把他倒过来写，也就是等价于求解 (c,-d) \to (a,-b)。

否则，不妨设 c,d > 0。

显然一定会出现某一个时刻满足 a',b' \ge 0。如果我们能找到这样一个位置，那么也就转化为最开始的情形了。

如果当前 a+b=0，那么下一步一定就会出现 (0,b) 或者 (a,0)，可以直接暴力检验。

否则，如果 a > -b，下一步可以是 (a+b,b)，也可以是 (a,a+b)。发现后者就满足我们所需的“出现 a',b' \ge 0”，检验他。

我们会不断执行 a \leftarrow a+b 直到 a \le -b。所以我们会对若干个 k 计算 (a+kb,a+(k+1)b) 如何转移到 (c,d)，最后令 a \leftarrow a+tb。

此时不妨设 a < -b。那么转移到 (a+b,b) 或者 (a,a+b)。前者没有任何前途，因为会直接出现 a',b' < 0。所以我们直接辗转相除跳到下一个端点即可。

但是我们会计算非常多次 (a,b) \to (c,d)，这及其不友好。

发现我们可以将这样的 (a,b) 划分为 O(\log V) 段，每一段的 a-b 为定值，且这个东西随着段的增加是递增的。

而将 (c,d) 反方向往前推的时候，c-d 在 c > d 的时候是严格递减的，所以可以直接维护几个等差数列，使用双指针优化即可做到 O(\log V) 单组询问。（不过你直接写 O(\log^2 V) 的能过，而且还挺快）

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int T,a,b,c,d;
int solve(int a,int b,int c,int d) {
    if(c<0||d<0) return -1;
    int ans=0;
    if(a==c&&b==d) return 0;
    while(c!=0&&d!=0) {
        if(c==d) {
            if(a==0&&b==c||a==c&&b==0) return ans+1;
            if(a==c&&b==d) return ans;
            return -1;
        }
        if(c<d) swap(c,d),swap(a,b);
        if(c%d==0&&(a==0&&b==d||a==d&&b==0)) return ans+c/d;
        if(b==d&&a<=c&&(c-a)%d==0) return ans+(c-a)/d;
        ans+=c/d,c%=d;
    }
    if(a==c&&b==d) return ans;
    return -1;
}
void check(int &ans,int mzx,int nv) {
    if(mzx==-1) return ;
    ans=min(ans,mzx+nv);    
}
struct INFO {int l1,l2,r,d;};
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>a>>b>>c>>d;
        if(a==c&&b==d) {cout<<0<<'\n';continue ;}
        if(a<=0&&b<=0) a=-a,b=-b,c=-c,d=-d;
        if(a>=0&&b>=0) {cout<<solve(a,b,c,d)<<'\n';continue ;}
        if(a<0) a=-a,b=-b,c=-c,d=-d;
        if(c>=0&&d<=0) {cout<<solve(c,-d,a,-b)<<'\n';continue ;}
        if(c<0) swap(a,b),swap(c,d),a=-a,b=-b,c=-c,d=-d;
        if(c<0&&d>0) {cout<<-1<<'\n';continue ;}
        vector<INFO> vc;
        int cc=c,dd=d;
        while(cc!=0&&dd!=0) {
            if(cc<=dd) {dd%=cc;continue ;}
            vc.push_back({cc%dd+dd,cc,dd,dd}),cc%=dd;
        }
        int v=__gcd(c,d);
        int ans=LONG_LONG_MAX,al=0;
        while(a>0&&b<0) {
            if(a+b==0) {check(ans,solve(a,0,c,d),al+1);break ;}
            if(a+b<0) {al+=(-b)/a,b=-((-b)%a);continue ;}
            if(-b==v) {
                int dl1=v,dl2=v,rr=0,ll=v;
                if(ll<=a&&(a-ll)%(-b)==0) check(ans,solve(ll,rr,c,d),al+(rr-a)/b);
            }
            for(auto id:vc) {
                int dl1=id.l1-id.r,dl2=id.l2-id.r;
                if(dl1<=-b&&-b<=dl2&&(-b-dl1)%id.r==0) {
                    int rr=id.r,ll=rr-b; 
                    if(ll<=a&&(a-ll)%(-b)==0) check(ans,solve(ll,rr,c,d),al+(rr-a)/b);
                }
            }
            al+=a/(-b),a=a%(-b);
        }
        if(a>=0&&b>=0) check(ans,solve(a,b,c,d),al);
        if(ans!=LONG_LONG_MAX) cout<<ans<<'\n';
        else cout<<-1<<'\n';
    }
    return 0;
}