题解：AT_arc222_f [ARC222F] Triple Transformation

· · 题解

参考资料

题意简述

对非负整数三元组 (x,y,z) 定义一次操作：

(x,y,z)\to \begin{cases} (x-y-z,2y,2z) & y+z<x \\ (2x,y-x-z,2z) & x+z<y \\ (2x,2y,z-x-y) & x+y<z \\ (y+z-x,x+z-y,x+y-z) & \text{otherwise} \end{cases}

给定 A=(A_1,A_2,A_3) 与 B=(B_1,B_2,B_3)，求把 A 变成 B 的最少操作次数，无法做到输出 -1。共 T 组，1\le T\le 300，0\le A_i,B_i\le 10^8。

解题思路

记 s=x+y+z。注意 y+z<x\iff 2x>s，上式可改写为：

(x,y,z)\to \begin{cases} (2x-s,2y,2z) & 2x>s \\ (2x,2y-s,2z) & 2y>s \\ (2x,2y,2z-s) & 2z>s \\ (s-2x,s-2y,s-2z) & \text{otherwise} \end{cases}

四种情形结果之和都是 s，故 s 是不变量；A,B 之和不等即输出 -1。s=0 时只有 (0,0,0)，答案为 0。

在模 s 下观察：前三种情形恰是逐坐标乘 2。以 2x>s 为例，2x-s\equiv 2x，且此时 y,z<\frac{s}{2}，2y,2z 已落在 [0,s) 内；故 (x,y,z)\to(2x,2y,2z)\pmod s。第四种情形是逐坐标乘 -2：s-2x\equiv -2x。合起来，一次操作把三元组模 s 乘以 2 或 -2。

反过来，结果由「和恰为 s」唯一确定。设三坐标模 s 的余数为 r_1,r_2,r_3，其和 \equiv 0\pmod s，即属于 \set{0,s,2s}：和为 s 时取 (r_1,r_2,r_3)（对应乘 +2），和为 2s 时取 (s-r_1,s-r_2,s-r_3)（对应乘 -2），和为 0 时是某个顶点。于是施加 K 次操作的结果 F^K(A)，就是与 2^KA 或 -2^KA 同余、且和为 s 的唯一非负三元组——操作是确定的，从 A 出发只有一条轨迹。答案即最小的 K 使 F^K(A)=B，否则 -1。

据此：

F^K(A)=B\iff 2^KA_i\equiv B_i\text{ or }2^KA_i\equiv -B_i\pmod s

两式都对所有 i 成立，且组内三坐标取同一符号。

若 s 为偶：任意一次操作后三坐标全偶（2x-s 与 s-2x 都是偶数）。又当三坐标全偶时「整组折半」与操作可交换，F(x,y,z)=2F(\frac{x}{2},\frac{y}{2},\frac{z}{2})，于是 F^K(A)=2F^{K-1}(\frac{1}{2}F(A))（在模 \frac{s}{2} 意义下）。所以走 K\ge 1 步要求 B 全偶，且问题降为把 \frac{1}{2}F(A) 变到 \frac{1}{2}B。反复折半直到 s 为奇，并累加偏移量。若某步 s 仍偶而 B 不全偶，则无法再前进，就此停止。

$$ 2^KA_1\equiv C_1,2^KA_2\equiv C_2\pmod s $$ 用 **大步小步算法**（Baby-Step Giant-Step，BSGS）求最小 $K$。设 $m=\lceil\sqrt s\rceil$，把 $K$ 写作 $K=im-j$（$0\le j<m$）：小步枚举 $j$，把 $(C_1\cdot2^j,C_2\cdot2^j)$ 连同 $j$ 存入哈希表；大步枚举 $i$，查 $(2^{im}A_1,2^{im}A_2)$。两坐标各在 $[0,s)$ 内，打包成单个键 $r_1s+r_2$ 即可（不超过 $s^2\le 9\times10^{16}$，`long long` 可容）。$i$ 自小到大、相同键保留较大的 $j$，首个命中即最小 $K$。 取 $C=B$ 总是有效；取 $C=-B$ 仅当 $B$ 三坐标全正——否则该符号对应的态和为 $s$ 而非 $2s$，并不等于 $B$（含 $0$ 坐标的 $B$ 只能由乘 $+2$ 到达）。两者取较小。 顶点（两坐标为 $0$、第三坐标为 $s$）是不动点：非顶点到不了顶点，顶点也只停在自身，单独判掉。 每组数据折半 $O(\log s)$、BSGS $O(\sqrt s)$。时间复杂度为 $O(T\sqrt s)$。 ## 参考代码 ```cpp #include <bits/stdc++.h> using namespace std; using ll=long long; const ll inf=0x3f3f3f3f3f3f3f3f; tuple<ll,ll,ll> F(tuple<ll,ll,ll> a) { auto [x,y,z]=a; ll s=x+y+z; if(2*x>s)return {2*x-s,2*y,2*z}; if(2*y>s)return {2*x,2*y-s,2*z}; if(2*z>s)return {2*x,2*y,2*z-s}; return {s-2*x,s-2*y,s-2*z}; } ll Pow(ll x,ll y,ll mod) { ll res=1; x%=mod; while(y) { if(y&1)res=(__int128)res*x%mod; x=(__int128)x*x%mod; y>>=1; } return res; } ll bsgs(ll a,ll b,ll c,ll d,ll s) { a%=s;b%=s;c%=s;d%=s; if(a==c&&b==d)return 0; ll m=sqrt(s)+1; unordered_map<ll,ll> mp; for(ll j=0;j<m;j++) { mp[c*s+d]=j; c=c*2%s;d=d*2%s; } ll t=Pow(2,m,s); for(ll i=1;i<=m;i++) { a=(__int128)a*t%s;b=(__int128)b*t%s; if(mp.count(a*s+b))return i*m-mp[a*s+b]; } return inf; } bool vtx(tuple<ll,ll,ll> a) { auto [x,y,z]=a; return (x==0)+(y==0)+(z==0)>=2; } ll core(tuple<ll,ll,ll> a,tuple<ll,ll,ll> b,ll s) { if(a==b)return 0; if(vtx(a)||vtx(b))return inf; auto [x,y,z]=a; auto [u,v,w]=b; ll res=bsgs(x,y,u,v,s); if(u&&v&&w)res=min(res,bsgs(x,y,(s-u)%s,(s-v)%s,s)); return res; } ll solve(tuple<ll,ll,ll> a,tuple<ll,ll,ll> b) { auto &[x,y,z]=a; auto &[u,v,w]=b; if(x+y+z!=u+v+w)return -1; ll s=x+y+z; if(!s)return 0; ll ans=inf,cnt=0; while(1) { if(a==b)ans=min(ans,cnt); if(s&1) { ll c=core(a,b,s); if(c<inf)ans=min(ans,cnt+c); break; } if((u|v|w)&1)break; a=F(a); x/=2;y/=2;z/=2; u/=2;v/=2;w/=2; s/=2;cnt++; } return ans<inf?ans:-1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin>>T; while(T--) { ll x,y,z,u,v,w; cin>>x>>y>>z>>u>>v>>w; cout<<solve({x,y,z},{u,v,w})<<'\n'; } return 0; } ```