P14027 加训加训 题解

Celenova · 2025-09-15 19:17:35 · 题解

题目传送门

题目大意

给你两个非负整数 a,b 与一个正整数 k，
每次操作你可以将 a 加上 k 或者乘以 k，
问最少几次操作后得到 b \le a。

思路

考虑贪心。

首先由于 a 与 b 都是非负整数，k 为正整数，显然正常情况下 a \times k 比 a+k 是更优的。
于是一直乘到 b \le a，输出次数就行了。

接下来考虑特殊情况：

1. k=1

   任何数乘一都为它本身，所以这时只能一步一步加上去了。

2. a=1$ 或 $a=0

   显然这两种情况都只能加不能乘。

代码

#include <bits/stdc++.h>
using namespace std;
int a,b,k,ans;
int main()
{
    cin>>a>>b>>k;
    while(a<b)
    {
        if(a==1||a==0||k==1) //特判
        {
            a+=k;
            ans++;
        }
        else
        {
            a*=k;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}