喵~ 各位初次见面或者好久不见的Master，大家好呀！我是你们的小助手猫娘~ 今天我们要一起来看看 Codeforces 上的一个很有趣的问题：1418A - Buying Torches。这道题就像是在为我们的洞穴探险做准备一样，很有代入感呢，喵！

那么，就让我们一起来看看怎么用最少的交易次数，做出足够多的火把来照亮前路吧！

题目大意

简单来说，我们在玩一个叫 Cubecraft 的游戏，一开始我们只有 1 根木棍。我们的目标是制作 k 个火把。

制作火把的配方很简单：

• 1 个火把 = 1 根木棍 + 1 块煤炭

为了获得足够的材料，我们可以和一个帅气的商人进行两种交易：

1. 换木棍：用 1 根木棍换来 x 根木棍。
2. 换煤炭：用 y 根木棍换来 1 块煤炭。

我们可以按任意顺序、任意次数进行这两种交易。问题是，为了最终能造出至少 k 个火把，我们最少需要进行多少次交易呢？

题解方法

要解决这个问题，我们得先理清思路，一步一步来分析，喵~

第一步：分析最终需要什么

我们的目标是制作 k 个火把。根据配方，这意味着我们最终手上必须要有 k 根木棍（用于制作）和 k 块煤炭。

第二步：分析如何获得煤炭

要获得 k 块煤炭，唯一的办法就是进行第二种交易。每交易一次获得 1 块煤炭，所以要获得 k 块煤炭，我们必须进行 k 次这种交易。这是固定不变的，没办法减少，喵。

那么，进行这 k 次煤炭交易所需要的代价是什么呢？每次交易需要 y 根木棍，所以总共需要 k * y 根木棍。

第三步：分析总共需要多少木棍

现在我们来算算总共需要多少根木棍吧！

1. 换 k 块煤炭需要 k * y 根木棍。
2. 制作 k 个火把本身也需要 k 根木棍。

所以，我们总共需要的木棍数量是 k * y + k。

第四步：分析如何获得木棍

我们一开始只有 1 根木棍。所以，我们需要通过交易来获得的木棍数量是 (k * y + k) - 1 根。

获得木棍只能通过第一种交易：用 1 根木棍换 x 根。每次交易，我们付出了 1 根，得到了 x 根，相当于净赚了 x - 1 根木棍。

现在问题就变成了：我们需要净赚 (k * y + k) - 1 根木棍，每次交易能净赚 x - 1 根，那么需要交易多少次呢？

这其实是一个向上取整的除法问题，喵。需要的交易次数是： ceil( (k * y + k - 1) / (x - 1) )

在程序里，为了避免使用浮点数带来的精度问题，我们可以用整数除法来实现向上取整。对于两个正整数 a 和 b，ceil(a / b) 可以写成 (a + b - 1) / b。

所以，获取木棍的交易次数就是 ((k * y + k - 1) + (x - 1) - 1) / (x - 1)，简化一下就是 (k * y + k - 2 + x) / (x - 1)。等等，猫娘的脑子有点绕晕了，用 (a + b - 1) / b 这个公式更直接喵！ 令 a = k * y + k - 1，b = x - 1，那么次数就是 (a + b - 1) / b。

第五步：计算总交易次数

最后一步，把两种交易的次数加起来！ 总交易次数 = (获取木棍的交易次数) + (获取煤炭的交易次数) 总交易次数 = ceil( (k * y + k - 1) / (x - 1) ) + k

这样，我们就得到了最少的总交易次数啦！是不是很简单呢，喵~

题解

下面是这个思路的 C++ 实现代码，猫娘加上了一些注释，方便 Master 理解哦。

#include <iostream>

void solve() {
    long long x, y, k;
    std::cin >> x >> y >> k;

    // 目标：制作 k 个火把，需要 k 根木棍和 k 块煤炭。

    // 为了获得 k 块煤炭，需要进行 k 次交易，
    // 这需要花费 k * y 根木棍。
    // 所以，我们总共需要 (k * y) [换煤炭] + k [做火把] = k * (y + 1) 根木棍。
    long long required_total_sticks = k * y + k;

    // 我们一开始有 1 根木棍，所以需要通过交易净获得 (required_total_sticks - 1) 根。
    long long required_net_sticks = required_total_sticks - 1;

    // 每次木棍交易，我们用 1 根换 x 根，净赚 (x - 1) 根。
    long long gain_per_stick_trade = x - 1;

    // 计算需要多少次木棍交易。这里是向上取整的除法，喵~
    // (a + b - 1) / b 是计算 ceil(a/b) 的一个常用整数技巧。
    long long num_stick_trades = (required_net_sticks + gain_per_stick_trade - 1) / gain_per_stick_trade;

    // 总交易次数 = 木棍交易次数 + 煤炭交易次数 (固定的 k 次)
    long long total_trades = num_stick_trades + k;

    std::cout << total_trades << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但也包含了一些在算法竞赛中非常有用的基础知识点哦，喵！

1. 贪心思想 (Greedy Approach) 这道题的解法本质上是一种贪心策略。我们分析出，为了最小化总交易次数，其中换煤炭的 k 次是不可避免的。因此，我们的目标就变成了最小化换木棍的次数。要最快地（用最少次数）获得足够多的木棍，我们自然应该每次都采用净收益最高的方式，也就是第一种交易。所以我们先计算出总共需要多少木棍，然后全部用第一种交易来换，这就是最优解啦，喵~

2. 向上取整的整数实现 在编程中，我们经常遇到需要向上取整的情况。比如 10 / 3 结果是 3.33...，如果我们需要装满 10 个东西，每个箱子装 3 个，那我们就需要 4 个箱子。这就是向上取整。 使用 ceil() 浮点函数有时会因为精度问题出错，而且效率较低。对于正整数 a 和 b，计算 ceil(a / b) 的一个绝佳方法是使用 (a + b - 1) / b。这个小技巧在竞赛中非常常用，Master 一定要记住哦！

3. 数据类型的重要性 (long long) 猫娘要特别提醒一下，题目中 x, y, k 的范围都很大，可以达到 10^9。在计算 k * y 时，结果可能会达到 10^18，这远远超过了普通 int 类型（大约 2 * 10^9）的表示范围。如果不使用 long long，就会导致数据溢出，得到错误的答案。所以在处理大数字时，一定要对数据范围保持敏感，选择合适的类型，喵！

好啦，今天的题解就到这里了！希望猫娘的讲解能对 Master 有所帮助。下次再见啦，喵~