首页 > 试题广场 >

乘除

[编程题]乘除

热度指数：260 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正整数 $A$ ，我们希望通过一些操作把它变成正整数 $B$ 。操作流程如下：初始数字为 $A$ ，每次可以将当前的数字乘以 $k$ ，或者除以 $k$ 。除以 $k$ 时上取整或者下取整由你决定（ $k$ 输入给定）。
形式化地：初始时执行 $x=A$ ，每次操作执行 $x = x \times k$ ， $x = \lfloor \frac{x}{k} \rfloor$ , $x=\lceil \frac{x}{k} \rceil$ 中的一种，最后要让 $x$ 的值等于 $B$
问至少需要几步操作（或者不可能达成）？

输入描述:

第一行一个正整数，表示数据组数。接下来行，每行三个正整数

输出描述:

对于每组数据，如果有解输出最少的操作数，否则输出

示例1

输入

输出

3
2
-1

说明

第一组数据
第二组数据

算法知识视频讲解

Sen🍓🍀

// 除法DFS：a/k多次 → t
static int INF = Integer.MAX_VALUE / 2;
static int dfs(int a, int t, int k) {
    if (a == t) return 0;
    if (a < t) return INF;
    return 1 + Math.min(dfs(a / k, t, k), dfs((a + k - 1) / k, t, k));
}

发表于 2025-10-29 19:40:30 回复(0)