G-一起铸最好的剑！_2025牛客寒假算法基础集训营2 题解

链接：https://ac.nowcoder.com/acm/contest/95334/G
来源：牛客网

题目描述

牛可乐从古籍中得知，铸剑的温度越接近n度，剑的品质越好。现在，他正在研究他家的铸剑炉，想要铸出全村最好的剑。
启动炉子时，牛可乐已经添过了一次柴，所以铸剑炉的初始温度为m度。此后，牛可乐每次添柴可以使得铸剑炉的温度提高到原来的m倍，即温度变为m^2, m^3, …

牛可乐想要知道，他最少需要添多少次柴（包括启动炉子时添的那一次），才能使得铸剑炉的温度最接近n度，这样他就能铸出一把品质最好的剑。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦105)代表数据组数，每组测试数据描述如下：

在一行上输入两个整数 n,m(1≦n,m≦10^9)代表最佳铸剑温度、牛可乐每次添柴可以使得铸剑炉的温度提高的倍数。

输出描述:

对于每组测试数据，新起一行。输出一个整数，代表牛可乐最少需要的添柴次数。                    

输入

3
7 6
6 2
9 9

输出

1
2
1

说明

对于第一组数据，牛可乐启动炉子时，铸剑炉的温度为 666 度，如果再添一次柴，铸剑炉的温度会达到36度，显然更劣。所以牛可乐只需要初始时添一次柴即可。
对于第二组数据，牛可乐启动炉子时，铸剑炉的温度为 222 度，此后每次添柴会使得火炉温度变为：4,8,16,32,⋯。

题解

需要注意到题目的数据有1≦n,m≦10^9， 而$2^32> 10^9$，因此我们只需要遍历32次即可

此外如何衡量ans是否合适？可以定义一个差值变量，不停的取小并更新ans

代码实现如下

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
int T,n,m;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        ll minEps=inf,ans,nowTemp=1;
        for(int i=1;i<=32;i++){
            if(nowTemp>=inf/m) break; //如果当前温度*m要比inf大了就break防止溢出
            nowTemp*=m;
            if(abs(n-nowTemp)<minEps){
                minEps=abs(n-nowTemp); //更新最小差值
                ans=i;
            }
        }
        cout<<ans<<endl;
    }
}