素晴らしき日々

 问题理解与转化#

1.题目概述#

• 有 n 个机器人 和 m 个能量棒，现在你能进行两个操作
  • 1.消灭一个机器人
  • 2.产生一个能量棒
• 要求操作后的 m1 % n1 == 0 的最小操作数

输入：

1
3
2
3 12
3
10 6
4
8 20

输出：

1
0
2
4
3
2

关键约束：$n, m \leq 10^8$ 数据量大，不支持一个个算，需要有一些快速的办法计算

问题理解: 题目问我们的是能分配的前提下，最小的操作数

• 操作数: $f(n`)=(n-n`)+(m`-m)$
• 能够分配: $m`=\lceil \frac{m}{n`} \rceil*n`$
• 根据这两个式子带入约化得到只包含 $n`$ 的函数表达式，故可以计算答案

2. 核心思路阐述#

3. 详细算法设计#

• 步骤分解：
  • 根据上面分析，我们只需要遍历所有$\lfloor \frac{m-1}{n`} \rfloor$ 所有可能的值，并将 $l$ 代入即可
  • 计算[l,r]: l从1开始，r取带入l与$\lfloor (m-1)/l \rfloor$ 相等的最大值
  • 设$v=\lfloor (m-1)/l \rfloor,r=\lfloor (m-1)/v \rfloor$
  • 用l带入式子得到答案，取min, l = r + 1 开始遍历查找.

1
    for(int l = 1, r; l <= n; l = r + 1){
2
        int v = x / l;
3
        //这里的 l 和 r 表示 选择[l, r]区间的任何数 floor((m-1)/i) 都相等
4
        r = (v == 0) ? n : min(n, x / v);  //数论分块理论
5
        ans = min(ans, n - m + l * (x / l));
6
    }

• 复杂度分析
  • $O(T*\sqrt{m})$ 每一个问题需要$\sqrt{m}$的时间计算

4. 正确性证明#

• 边界情况：选择全增加能量棒$(n-m\%n)$

• 特殊情况：当$n>m$时，由于n只能减少，m只能增加，故最小的操作数就是$n-m$

• 数学证明： $\lceil \frac{m}{n`} \rceil-1=\lfloor \frac{m-1}{n`} \rfloor$ 设 $m = q n' + r$，其中 $0 \le r < n'$，$q$ 为整数。

• 若 $r = 0$（$m$ 被 $n'$ 整除）：
  左边 $\lceil m/n' \rceil - 1 = q - 1$；
  右边 $\lfloor (m-1)/n' \rfloor = \lfloor (q n' - 1)/n' \rfloor = \lfloor q - 1/n' \rfloor = q - 1$。

• 若 $r \ge 1$：
  左边 $\lceil m/n' \rceil - 1 = (q + 1) - 1 = q$；
  右边 $\lfloor (m-1)/n' \rfloor = \lfloor (q n' + r - 1)/n' \rfloor = \lfloor q + (r-1)/n' \rfloor = q$
  （因为 $0 \le r-1 < n'$，故 $(r-1)/n' < 1$）。

5. 复杂度分析#

• 时间复杂度：计算单个答案$\sqrt{m}$

• 空间复杂度：(忽略)

• 实际性能：$O(T*\sqrt m)$

6. 代码实现#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
#define int long long
5
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
6
#define x first
7
#define y second
8
#define endl "\n"
9
typedef signed long long LL;
10
typedef pair<int, int> PII;
11

12
const int N = 1e5 + 10;
13
//f(n`) = (n - n`) + (m` - m)
14
// 注意：这里的公式推导
15
// 原式 = (n-i) + (ceil(m/i)*i - m)
16
// = n - m + i * (ceil(m/i) - 1)
17
// = n - m + i * floor((m-1)/i)
18
// 所以代价是 ans = min(ans, n - m + l * v);
19
void solve() {
20
    int n, m;
21
    cin >> n >> m;
22
    if(n > m) {
23
        cout << n - m << endl;
24
        return;
25
    }
26
    int x = m - 1;
27
    int ans = (n - m % n) % n; //全部都添加 能量棒
28
    for(int l = 1, r; l <= n; l = r + 1){
29
        int v = x / l;
30
        //这里的 l 和 r 表示 选择[l, r]区间的任何数 floor((m-1)/i) 都相等
31
        r = (v == 0) ? n : min(n, x / v);  //数论分块理论
32
        ans = min(ans, n - m + l * (x / l));
33
    }
34
    cout << ans << endl;
35
}
36

37
signed main(){
38
    IOS;
39
    int _ = 1;
40
    cin >> _;
41
    while(_--){
42
        solve();
43
    }
44
}

7. 常见错误与陷阱#

• 易错点分析：数学公式计算容易出错，要对**数论分块（整除分块）**有一定理解

• 调试技巧：公式的验证

8. 拓展与变种#

• 相关问题：暂无

• 实际应用：计算数学整除的一些问题

9. 总结与收获#