小O的整数操作

[编程题]小O的整数操作

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

小O有一个整数 $n$ ，她每次可以进行以下操作之一：
1. 将 $n$ 减去 $1$ ；
2. 将 $n$ 除以 $k$ （当 $n$ 可以被 $k$ 整除时）。

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

输入描述:

在一行上输入三个整数  和  表示初始数字、目标数字和 可以除的数字。

输出描述:

在一行上输出一个正整数，表示将  变成  至少需要多少次操作。

示例1

输入

10 4 2

输出

说明

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

算法知识视频讲解

次饭没

def min_operations(n, m, k):
    if n <= m:
        return n - m
    count = 0
    while n > m:
        if k == 1:
            count += (n - m)
            break
        remainder = n % k
        if remainder != 0:
            # 非整除场景：保持原有逻辑不变
            if n - remainder <= m:
                count += (n - m)
                n = m
            else:
                count += remainder
                n -= remainder
        else:
            # 核心修正：预判整除结果是否小于m
            divided_n = n // k  # 计算整除后的结果
            if divided_n < m:
                # 若整除结果小于m，放弃整除，直接减到m
                count += (n - m)
                n = m  # 更新n为m，终止后续循环
            else:
                # 若整除结果大于等于m，再执行整除操作
                count += 1
                n = divided_n
    return count

发表于今天 20:37:18 回复(0)