首页 > 试题广场 >

小O的整数操作

[编程题]小O的整数操作
  • 热度指数:248 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小O有一个整数 n,她每次可以进行以下操作之一:
1. 将 n 减去 1
2. 将 n 除以 k(当 n 可以被 k 整除时)。

小O想知道,将 n 变成 m 至少需要多少次操作。

输入描述:
在一行上输入三个整数 n,mk\ ( 1 \leq m \leq n \leq 10^9;\ 1 \leq k \leq 10^9 ) 表示初始数字、目标数字和 可以除的数字。


输出描述:
在一行上输出一个正整数,表示将 n 变成 m 至少需要多少次操作。
示例1

输入

10 4 2

输出

2

说明

先将 10 除以 2 得到 5,再将 5 减去 1 得到 4,共需要 2 次操作。

头像 AoeKeller
发表于 2025-08-16 10:48:01
const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () = 展开全文
头像 丨阿伟丨
发表于 2025-09-11 17:42:11
题目链接 小O的整数操作 题目描述 给定三个整数 , , 和 。初始时我们有一个数字 ,目标是将其变为 。 我们有两种操作: 将当前数字减去 1。 如果当前数字能被 整除,可以将其除以 。 求解将 变为 所需的最少操作次数。 解题思路 这是一个典型的最短路问题,可以使用广度优先搜索(BFS 展开全文