C. K-th Not Divisible by n - 题解

比赛与标签

比赛: Codeforces Round 640 (Div. 4) 标签: binary search, math 难度: *1200

喵喵，题目在说什么呀？

这道题目的要求其实非常直接明了呐！它会给我们两个正整数 n 和 k。我们的任务就是，在所有正整数中，找到第 k 个不能被 n 整除的数，然后把它打印出来。

举个栗子🌰：如果 n=3, k=7，那么所有不能被 3 整除的数是：1, 2, 4, 5, 7, 8, 10, ... 像这样无限延伸下去。我们数一数，第 7 个数正好是 10，所以我们就要输出 10 啦！

简单来说，就是：

• 输入: t 组测试数据，每组包含 n 和 k。
• 输出: 对每组输入，输出那个万中挑一的、第 k 个不被 n 整除的数。

小猫娘的解题思路~

嘿嘿，这道题可以用纯粹的数学方法来解决，也可以用二分查找的思路哦！我们先来探索一下其中美妙的数学规律吧！

数学规律发现之旅！

我们来观察一下数字的分布规律。在从 1 开始的数轴上，每 n 个数（比如 1 到 n，n+1 到 2n）就是一个周期。在这个周期里，有 n-1 个数是不能被 n 整除的，只有 1 个数（也就是 n 的倍数）可以被 n 整除。

这就像我们在一条路上捡宝藏，但每走 n-1 步就会遇到一个需要绕开的陷阱（n的倍数）。我们想捡到第 k 个宝藏，需要走多远呢？

我们想要的第 k 个数，可以看作是 k 个“好数”（不能被n整除的数）。为了得到这 k 个好数，我们必然要跳过一些“坏数”（能被n整除的数）。那么问题就变成了：为了凑齐 k 个好数，我们到底需要跳过多少个坏数呢？

每 n-1 个好数，就对应着 1 个被我们跳过的坏数。所以，我们可以把好数们分成 n-1 个一组。k 个好数里包含了多少个完整的“n-1 个好数”的组呢？

这个数量就是 (k-1) / (n-1)（这里用整除哦！）。为什么是 k-1 呢？因为第 k 个数本身可能是一个新组的开头，我们只关心在它之前有多少个 完整 的组。

举个例子 n=3, k=7：

• 好数组的大小是 n-1 = 2。
• 我们要找第 7 个好数。
• 在找到它之前，我们经过了 (7-1)/(3-1) = 6/2 = 3 个完整的组。
• 每个完整的组都意味着我们跳过了一个坏数（3的倍数）。所以我们总共跳过了 3 个坏数（它们分别是 3, 6, 9）。
• 那么，第 7 个好数的位置，就是在 k 的基础上，加上我们跳过的坏数的数量。
• 最终的答案就是 k + (我们跳过的坏数数量) = k + (k-1)/(n-1)。
• 代入数值：7 + (7-1)/(3-1) = 7 + 3 = 10。Bingo！完全正确！

所以，我们就得到了一个超级优雅的公式！

另一种思路：二分查找喵~

虽然数学公式很棒，但二分查找也是一个非常通用的强大工具哦！ 我们可以定义一个函数 count(x)，它能计算出从 1 到 x 中有多少个数不能被 n 整除。这个数量很容易算，就是 x - (x / n)。

我们发现，count(x) 是一个随着 x 增大而增大的函数（单调递增）。我们想找的是一个最小的 ans，使得 count(ans) = k。更准确地说，是最小的 ans 使得 count(ans) >= k，并且 count(ans-1) < k。

这不就是二分查找的经典应用场景嘛！

1. 我们设定一个很大的查找范围，比如 [1, 2*10^9]（一个足够大的数）。
2. 取中间值 mid，计算 count(mid)。
3. 如果 count(mid) < k，说明 mid 太小了，我们需要在右半边 [mid+1, high] 继续查找。
4. 如果 count(mid) >= k，说明 mid 可能就是答案，或者答案在它的左边，我们尝试在 [low, mid] 中寻找更小的答案。
5. 不断缩小范围，直到找到最终的答案。

虽然二分查找也能解决问题，但对于这道题，直接的数学推导显然更简洁高效，是一个 O(1) 的完美解法呢！

代码实现时刻！

下面就是用我们推导出的神奇公式写出的AC代码啦！注释里有小猫娘的贴心讲解哦~

#include <iostream>

// 这个函数用来解决单个测试用例，喵~
void solve() {
    long long n, k;
    std::cin >> n >> k;

    // 我们要找第 k 个不能被 n 整除的正整数。
    //
    // 分析一下数字的规律：
    // 在每 n 个连续的整数中，有 n-1 个数不能被 n 整除。
    //
    // 我们可以把这 n-1 个数看成一个“好数”分组。
    // 为了找到第 k 个好数，我们需要经过多少个完整的“好数组”呢？
    // 这个数量就是 (k - 1) / (n - 1) 啦！
    // 比如 n=3, k=7，好数组大小是 2。要找到第 7 个，需要经过 (7-1)/2 = 3 个完整的组。
    //
    // 每经过一个完整的“好数组”，就意味着我们跳过了一个“坏数”（n的倍数）。
    // 所以，跳过的坏数数量就是 (k - 1) / (n - 1)。
    //
    // 因此，第 k 个好数的真实值，就是 k 本身，再加上我们为了凑够k个好数而跳过的那些坏数的数量。
    // 最终的魔法公式就是：k + (k - 1) / (n - 1)
    //
    // 举个栗子 n=3, k=7:
    // result = 7 + (7 - 1) / (3 - 1) = 7 + 6 / 2 = 7 + 3 = 10。正确喵！
    //
    // 再举个栗子 n=4, k=12:
    // result = 12 + (12 - 1) / (4 - 1) = 12 + 11 / 3 = 12 + 3 = 15。也正确喵！
    //
    // 注意！n 和 k 很大，结果可能会超过 int 的范围，所以必须用 long long 来存储，不然会溢出哦！
    long long result = k + (k - 1) / (n - 1);
    std::cout << result << 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;
}

复杂度分析的说

• 时间复杂度: O(1) 的说。对于每一个测试用例，我们都只是执行了一次简单的算术运算。所以，总的时间复杂度是 O(t)，其中 t 是测试用例的数量。超级快！
• 空间复杂度: O(1) 的说。我们只用了几个变量来存储 n, k 和结果，没有使用额外的、随输入规模变大的空间。非常节省内存呢！

知识点与总结喵~

这道题虽然看似简单，但里面蕴含的智慧可不少哦！

1. 数学建模: 核心在于发现数字序列中的周期性规律，并将问题转化为一个简单的数学公式。这是数论问题中常见的思路，学会观察和归纳非常重要！
2. 逆向思维: 我们不是直接去数第 k 个数，而是思考“为了得到第 k 个目标数，需要跳过多少个非目标数”，这种逆向思维有时能让问题豁然开朗。
3. 数据类型的重要性: 千万要注意题目给出的数据范围！n 和 k 都是 10^9 级别，它们的和或积很容易超出 int 的表示范围（大约 2*10^9）。使用 long long 是避免“WA on test X”的护身符哦！
4. 二分查找的适用性: 即使我们找到了数学解，也别忘了这道题的另一个标签是 binary search。对于任何满足“答案单调性”的问题（即答案越大，某个评判标准也越大/小），二分查找都是一个值得考虑的通用解法。

好啦，今天的解题分享就到这里啦！希望大家都能从中学到新知识，感受到算法的魅力！如果还有什么问题，随时都可以来找小猫娘哦~ 下次再见，喵~ 👋