参考资料

• 离散对数 - OI Wiki

题意简述

对非负整数三元组 $(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$ 不全偶，则无法再前进，就此停止。

$s$ 为奇时 $2$ 模 $s$ 可逆。三条同余式中，第三条由前两条与「和 $\equiv 0$」自动成立（$2^K(A_1+A_2+A_3)\equiv 0$），只需：

$$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)$。

参考代码

1.63 KBcpp

#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;
}