题目链接

乘除

题目描述

给定三个正整数 。我们希望通过一些操作将 变成 。操作流程如下：

  • 初始数字为 。
  • 每次可以将当前的数字 变为以下三种之一：
    2. (向下取整)
    3. (向上取整)

问至少需要几步操作才能将 变成 ？如果不可能达成，则输出 -1。

解题思路

这是一个典型的在隐式图上寻找最短路径的问题，非常适合使用广度优先搜索 (BFS)。然而，由于数值范围可以达到 ，直接进行 BFS 可能会导致状态空间过大。

我们需要发现一个关键性质来优化搜索：任何最优路径，必然是先进行若干次除法操作，再进行若干次乘法操作。

为什么呢？可以这样考虑：

  • 一次乘法后紧接着一次除法（例如 ）是没有意义的，因为它会回到原点，浪费了两步。
  • 路径中可能出现类似 的情况，这可能是一个有效的中间步骤。

基于这个观察，我们可以将整个过程分解为两个阶段：

  1. 除法阶段：从初始值 开始，只通过除法（向下或向上取整）到达某个中间值 。
  2. 乘法阶段：从中间值 开始，只通过乘法到达目标值 。

这意味着 必须可以由 乘以若干次 得到，即 （其中 是乘法次数）。因此，所有可能的中间值 都必须是 中的一个（前提是能够整除）。

我们的解题策略如下：

  1. 枚举所有可能的中间目标 。这些 是通过从 开始不断除以 得到的序列。
  2. 对于每一个 ，我们计算从 只通过除法操作到达 的最短步数。这个子问题可以用一个 BFS (bfs_div) 来解决。
  3. bfs_div(n, t) 的步数，加上从 到 所需的乘法步数，就是一条完整的路径长度。
  4. 我们在所有可能的 中，找到总步数最少的那一个。

bfs_div 的实现有一个重要的优化：因为除法操作（对于 ）不会使数值增加，所以在从 向 搜索时，如果当前数值已经小于 ，那么就不可能再通过除法回到 了，可以直接剪掉这个分支。

代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;
using LL = long long;

// 只使用除法的BFS
int bfs_div(LL start, LL end, LL k) {
    if (start == end) {
        return 0;
    }
    map<LL, int> dist;
    queue<LL> q;

    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        LL curr = q.front();
        q.pop();

        // 向上取整
        LL next_ceil = (curr + k - 1) / k;
        if (dist.find(next_ceil) == dist.end()) {
            if (next_ceil == end) return dist[curr] + 1;
            // 剪枝：如果除法结果比目标还小，不可能到达了
            if (next_ceil > end) {
                dist[next_ceil] = dist[curr] + 1;
                q.push(next_ceil);
            }
        }

        // 向下取整
        LL next_floor = curr / k;
        if (dist.find(next_floor) == dist.end()) {
            if (next_floor == end) return dist[curr] + 1;
            if (next_floor > end) {
                dist[next_floor] = dist[curr] + 1;
                q.push(next_floor);
            }
        }
    }
    return -1;
}

void solve() {
    LL n, m, k;
    cin >> n >> m >> k;

    if (n == m) {
        cout << 0 << "\n";
        return;
    }
    if (k == 1) {
        cout << -1 << "\n";
        return;
    }

    LL ans = -1;

    // 枚举乘法次数
    LL mul_steps = 0;
    LL target = m;
    while (true) {
        if (n >= target) {
            int div_steps = bfs_div(n, target, k);
            if (div_steps != -1) {
                if (ans == -1 || div_steps + mul_steps < ans) {
                    ans = div_steps + mul_steps;
                }
            }
        }
        
        if (target % k != 0) {
            break;
        }
        target /= k;
        mul_steps++;
    }

    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;

public class Main {
    // 只使用除法的BFS
    static int bfs_div(long start, long end, long k) {
        if (start == end) {
            return 0;
        }
        Map<Long, Integer> dist = new HashMap<>();
        Queue<Long> q = new LinkedList<>();

        q.add(start);
        dist.put(start, 0);

        while (!q.isEmpty()) {
            long curr = q.poll();
            int d = dist.get(curr);

            // 向上取整
            long next_ceil = (curr + k - 1) / k;
            if (!dist.containsKey(next_ceil)) {
                if (next_ceil == end) return d + 1;
                if (next_ceil > end) {
                    dist.put(next_ceil, d + 1);
                    q.add(next_ceil);
                }
            }

            // 向下取整
            long next_floor = curr / k;
            if (!dist.containsKey(next_floor)) {
                if (next_floor == end) return d + 1;
                if (next_floor > end) {
                    dist.put(next_floor, d + 1);
                    q.add(next_floor);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            long m = sc.nextLong();
            long k = sc.nextLong();

            if (n == m) {
                System.out.println(0);
                continue;
            }
            if (k == 1) {
                System.out.println(-1);
                continue;
            }

            long ans = -1;
            long mul_steps = 0;
            long target = m;

            while (true) {
                if (n >= target) {
                    int div_steps = bfs_div(n, target, k);
                    if (div_steps != -1) {
                        if (ans == -1 || div_steps + mul_steps < ans) {
                            ans = div_steps + mul_steps;
                        }
                    }
                }
                
                if (target % k != 0) {
                    break;
                }
                target /= k;
                mul_steps++;
            }
            System.out.println(ans);
        }
    }
}

import collections

# 只使用除法的BFS
def bfs_div(start, end, k):
    if start == end:
        return 0
    
    q = collections.deque([(start, 0)])
    visited = {start}
    
    while q:
        curr, dist = q.popleft()
        
        # 向上取整
        next_ceil = (curr + k - 1) // k
        if next_ceil not in visited:
            if next_ceil == end:
                return dist + 1
            if next_ceil > end:
                visited.add(next_ceil)
                q.append((next_ceil, dist + 1))

        # 向下取整
        next_floor = curr // k
        if next_floor not in visited:
            if next_floor == end:
                return dist + 1
            if next_floor > end:
                visited.add(next_floor)
                q.append((next_floor, dist + 1))
    
    return -1

def solve():
    n, m, k = map(int, input().split())

    if n == m:
        print(0)
        return
    if k == 1:
        print(-1)
        return

    ans = -1
    mul_steps = 0
    target = m

    while True:
        if n >= target:
            div_steps = bfs_div(n, target, k)
            if div_steps != -1:
                if ans == -1 or div_steps + mul_steps < ans:
                    ans = div_steps + mul_steps
        
        if target % k != 0:
            break
        target //= k
        mul_steps += 1
        
    print(ans)


t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：数学、广度优先搜索 (BFS)
  • 时间复杂度：主循环迭代次数为 。在循环内部，我们执行一个只进行除法的 BFS。由于数值单调递减，bfs_div 的状态空间非常有限，其复杂度大致为 。因此，每个测试用例的总时间复杂度为 。
  • 空间复杂度：bfs_div 中用于记录访问状态的哈希表或队列，大小为 。因此，空间复杂度为 。