题解归档 - cf2236C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2236C
• 本地来源：problems/cf2236C/idea.md
• 题目链接：https://codeforces.com/contest/2236/problem/C

思路

pattern:
monotone operation normalization
claim:
It is enough to repeatedly divide the currently larger number and, before each division, try finishing by adding the difference to the smaller number.
why:
For a fixed number of division operations on each side, additions can be postponed until after those divisions: adding before a floor division costs at least as much as adding the resulting quotient increase afterwards. So an optimum is divide a i times, divide b j times, then add abs(a_i-b_j).
why greedy scan:
The sequences after repeated division are nonincreasing. Scanning the two sequences by always advancing the currently larger value visits the only candidates where the absolute difference can improve, and also covers the exact meeting case.
brute/check:
For small values, BFS over states matches the formula. A separate check against full enumeration of all division counts also matched small ranges and random large values.
edge:
Division may produce 0; meeting at 0 is allowed by the operation sequence, and the loop handles it.

代码

来源：problems/cf2236C/solution.cpp

/* Author: likely
 * Time: 2026-06-19 10:49:39
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll a,b,x,i,ans;
int main(){
    ll t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&a,&b,&x);
        ans=inf;
        i=0;
        while(a!=b){
            if(b>a) swap(a,b);
            ans=min(ans,llabs(a-b)+i);
            a/=x;
            i++;
        }
        ans=min(ans,i);
        printf("%lld\n",ans);
    }
    return 0;
}