暑假集训系列题解（十四）

暑假集训系列题解（十四）

题目1

题目链接

问题 F: Fair Distribution

题目描述

There are n robots and m energy bars in the Dream Kingdom. DreamGrid, the king, is trying to make a fair distribution of the energy bars. A fair distribution exists if and only if the number of the energy bars is a multiple of the number of robots.

The only tool DreamGrid has is a powerful laser gun. Every time he turns on the laser gun, he can do exactly one of the two things:

Create a new energy bar.

Destroy a robot.

To avoid the extinction of robots, it's forbidden to destroy all the n robots. It takes one dollar to turn on the laser gun once. You are asked to find the minimum cost of making a fair distribution.

输入

There are multiple test cases. The first line of the input contains an integer T (1≤T≤1000), indicating the number of test cases. For each test case:

The only line contains two integers n and m (1≤n,m≤108), indicating the initial number of robots and energy bars.

输出

For each test case output one line containing an integer, indicating the minimum cost to get a fair distribution.

样例输入

3
3 12
10 6
8 20

样例输出

0
4
2

提示

For the third sample, the best way is to destroy a robot and create an energy bar. After that, we have 7 robots and 21 energy bars, which leads to a fair distribution.

题解

枚举机器人少了x个，则可得当前的答案：

$n-(n-x)+(\frac{m+n-x-1}{n-x})*(n-x)-m=n-m+\frac{m-1}{n-x}*(n-x)$

其中 $\frac{m-1}{n-x}*(n-x)$可以由整数分块得到，类似于$\sum{\frac{n}{i}}$，最后统计答案取最小值即可。

参考博客：https://blog.csdn.net/qq_50377393/article/details/119151746

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        if (n >= m)
        {
            printf("%d\n", n - m);
            continue;
        }
        int ans = 0x3f3f3f3f;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, (m - 1) / ((m - 1) / l));
            ans = min(ans, n - m + (m - 1) / l * l);
        }
        printf("%d\n", ans);
    }
}