P14826 踩踩标

发表于 2025-12-22 更新于 2026-01-11

P14826 踩踩标

题目描述

现在题库里有 $n$ 道题，你想要刷穿整个题库。你会按以下过程进行训练：

套题训练：打 $b$ 场每场有 $a$ 题的模拟赛。模拟赛可以提升你的效率，你打完所有模拟赛后的思维能力提升 $a+b$ 点。显然，这些比赛的题目不会重合，总题数也不会超过 $n$ 道。
单题训练：对于没有被刷过的每道题目，你都可以提升 $k$ 点思维能力。

由于你很颓，所以你想知道在所有 $a,b$ 中，最少可以让你提升多少点思维能力。

形式化题意：给定 $n,k$，求所有使得 $n=ab+c$ 的自然数三元组 $(a,b,c)$ 中，$a+b+kc$ 的最小值。

输入格式

本题单个测试点内包含多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数 $n,k$，代表一组测试数据。

输出格式

对于每组测试数据输出一行，即最少的提升点数。

输入输出样例 #1

输入 #1

输出 #1

1
2
3

15
2
0

说明/提示

样例解释

对于第一组测试数据，组 $7$ 场每场有 $7$ 道题的比赛，并进行 $1$ 次单题训练。总提升为 $7+7+1=15$ 点。可以证明不存在提升更少的方案。

对于第三组测试数据，直接进行单题训练不会提升思维能力。

数据范围

记单个测试点内 $n$ 的总和为 $N$。

对于 $100\%$ 的数据，保证 $1\le T\le 10^5$，$1\le n,N\le 10^{12}$，$0\le k\le 10^6$。

测试点编号	$N\le$	特殊性质
$1,2$	$1000$	无
$3,4$	$10^6$	无
$5,6$	$10^{12}$	有
$7\sim 10$	$10^{12}$	无

特殊性质：$n$ 为完全平方数。

问题简述

给定 $n,k$，求所有自然数 $(a,b,c)$ 满足 $n = a \times b + c$ 时，$a + b + k \cdot c$ 的最小值。

核心思路

1. 特判 $k = 0$

若 $k = 0$，可取 $a = b = 0,\ c = n$，得 $a + b + k \cdot c = 0$，直接输出 0。

2. 一般情况 ($k > 0$)

对于固定的 $a$，为了最小化 $a + b + k \cdot c$，应让 $b$ 尽量大（从而 $c$ 尽量小），因为 $k > 0$。
因此最优 $b = \lfloor n/a \rfloor$，对应 $c = n - a \cdot b$。

关键问题：为什么需要两个循环？

疑问：$a$ 和 $b$ 都是乘法的因数，看起来对称，为什么不能只枚举 $a \le \sqrt{n}$？

原因：目标函数中的 $c$ 取决于 被除数 $a$（或 $b$）的余数，而不仅仅是乘积 $a \cdot b$。

具体来说：

当我们枚举 $a$ 时，计算 $b = \lfloor n/a \rfloor$，余数 $c = n \% a$。
当我们枚举 $b$ 时，计算 $a = \lfloor n/b \rfloor$，余数 $c = n \% a$。

这两者不同：$n \% a$ 与 $n \% b$ 一般不相等。
因此，只枚举 $a \le \sqrt{n}$ 会漏掉那些 $a > \sqrt{n}$ 但 $n \% a$ 很小的情况。

例子说明

设 $n = 10$，$k = 1$。

若只枚举 $a \le \sqrt{10} \approx 3$：
- $a=1,\ b=10,\ c=0$ → 值 $1+10+0=11$
- $a=2,\ b=5,\ c=0$ → 值 $2+5+0=7$
- $a=3,\ b=3,\ c=1$ → 值 $3+3+1=7$
  最优值为 $7$。
但考虑 $a=9$（$> \sqrt{10}$）：
- $b = \lfloor 10/9 \rfloor = 1$
- $c = 10 \% 9 = 1$
- 值 $9+1+1=11$，不如 $7$ 优。

这个例子中 $a> \sqrt{n}$ 没有更优，但可能存在其他 $n,k$ 使 $a> \sqrt{n}$ 更优。

覆盖所有情况的技巧

对于任意 $(a,b)$，至少有一个 $\le \sqrt{n}$（因为若 $a > \sqrt{n}$ 且 $b > \sqrt{n}$，则 $a \cdot b > n$，矛盾）。
因此：

第一层循环：枚举 $a = 1 \dots \sqrt{n}$，计算 $b = \lfloor n/a \rfloor$，更新答案。
第二层循环：枚举 $b = 1 \dots \sqrt{n}$，计算 $a = \lfloor n/b \rfloor$，更新答案。

这两个循环合起来，所有可能的 $(a,b)$ 对都被覆盖。

算法步骤

若 $k = 0$，输出 0。
初始化答案 ans = n * k（对应 $a = b = 0$）。
循环 $a$ 从 $1$ 到 $\sqrt{n}$：
- $b = n / a$（整除）
- $c = n - a * b$
- ans = min(ans, a + b + c * k)
循环 $b$ 从 $1$ 到 $\sqrt{n}$：
- $a = n / b$（整除）
- $c = n - a * b$
- ans = min(ans, a + b + c * k)
输出 ans。

代码（简洁版）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long T, n, k;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        if (k == 0) { cout << "0\n"; continue; }
        long long ans = n * k;
        for (long long a = 1; a * a <= n; a++) {
            long long b = n / a, c = n - a * b;
            ans = min(ans, a + b + c * k);
        }
        for (long long b = 1; b * b <= n; b++) {
            long long a = n / b, c = n - a * b;
            ans = min(ans, a + b + c * k);
        }
        cout << ans << "\n";
    }
    return 0;
}

时间复杂度

每组数据循环 $2\sqrt{n}$ 次，即 $O(\sqrt{n})$。
$n \le 10^{12}$ 时 $\sqrt{n} \le 10^6$，可接受。

总结

两个循环分别枚举 $a$ 和 $b$，确保所有 $(a,b)$ 对都被检查。
核心原因是余数 $c$ 依赖于被除数，而 $a,b$ 在余数计算中不等价。