C. Omsk Programmers 题解
思路
操作有两种：
- 给
a或b加1； - 把
a或b变成floor(value / x)。
关键结论：对任意一个数，如果一段操作里一共做了k次除法和若干次+1，那么这些+1都可以放到所有除法之后做，答案不会变差。
原因是：一次+1如果放在后续除法之前，它对最终结果的贡献最多也只是让最终值增加1；把它放到最后，同样花费一次操作，至少不会更差。
所以，对于一个初始值n，我们只需要考虑：
n, floor(n / x), floor(n / x^2), ...如果做了i次除法，当前值是A_i = floor(a / x^i)；
如果做了j次除法，当前值是B_j = floor(b / x^j)。
之后只需要把较小的那个数加到较大的那个数，总代价为：
i + j + abs(A_i - B_j)因此枚举a和b重复除以x后能得到的所有值，取上式最小值即可。
因为a, b <= 10^9，且x >= 2，每个数最多只会产生约30个不同层级，所以直接双重枚举即可。
正确性证明
引理 1
固定一个初始值n，如果某个操作序列中有k次除法和m次加一操作，并且最终得到y，那么存在另一个操作序列：先做k次除法，再做若干次加一操作，花费不超过原序列，并且也能得到y。
证明：
先只看这k次除法，不做任何加一操作，最终值为floor(n / x^k)。
原序列中的每次加一操作，即使放在除法之前，它对最终值的提升也最多为1。所以如果原序列最终得到y，必然有：
y >= floor(n / x^k) y - floor(n / x^k) <= m于是我们可以先做k次除法，再做y - floor(n / x^k)次加一操作，花费不超过k + m。
引理成立。
引理 2
若a做i次除法得到A_i，b做j次除法得到B_j，那么在这两个除法次数固定时，最小额外加一次数是abs(A_i - B_j)。
证明：
除法结束后，两个数分别是A_i和B_j。之后只能加一，所以最终公共值不能小于二者最大值。取公共值为max(A_i, B_j)时，较小者加到较大者，花费正好是：
max(A_i, B_j) - min(A_i, B_j) = abs(A_i - B_j)这是最小的。
定理
答案等于：
min(i + j + abs(A_i - B_j))其中A_i = floor(a / x^i)，B_j = floor(b / x^j)。
证明：
由引理 1，存在最优方案，使得每个数都是先做若干次除法，再做若干次加一操作。
设最优方案中a做了i次除法，b做了j次除法。由引理 2，在这组i, j固定时，最优代价就是：
i + j + abs(A_i - B_j)枚举所有可能的i, j并取最小值，就一定能得到全局最优答案。
复杂度
每个数最多被除到0，层数为O(log_x n)。
单个测试用例复杂度：
O(log_x a * log_x b)在本题范围内最多约31 * 31次枚举。
C++17 代码
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cin>>t;while(t--){longlonga,b,x;cin>>a>>b>>x;vector<pair<longlong,longlong>>va,vb;longlongcur=a;for(longlongcnt=0;;cnt++){va.push_back({cur,cnt});if(cur==0)break;cur/=x;}cur=b;for(longlongcnt=0;;cnt++){vb.push_back({cur,cnt});if(cur==0)break;cur/=x;}longlongans=llabs(a-b);for(auto[av,ai]:va){for(auto[bv,bi]:vb){ans=min(ans,ai+bi+llabs(av-bv));}}cout<<ans<<'\n';}return0;}
