Fair Distribution(2021 ZJCPC)

传送门

题目大意

有\(t\)组询问，每组询问有\(n\)个机器人和\(m\)块能量棒，定义合理分配当且仅当\(m\)是\(n\)的倍数。现在你有两种操作：\(1、\)使\(n\)的大小减少\(1\)；\(2、\)使\(m\)的大小增加\(1\)。每次操作都要消耗\(1\)元，问达到合理分配的最小花费是多少。\((1\leq t\leq1000,1\leq n,m\leq 10^8)\)

思路

这道题一眼看过去想到的是\(BFS\)，但是数据范围太大了，即使不\(MLE\)也会\(T\)，于是只好换个方向入手。首先很容易发现的是当\(m\leq n\)是答案就是\(n-m\)，然后我们看一下把\(n\)减小\(a(0\leq a< n)\)的情况，这时候\(m\)就需要增加到\({\lceil {m\over n-a}\rceil}*(n-a)\)，即\(m\)需要增加\(\lceil {m\over n-a}\rceil*(n-a)-m\)，现在令\(i=n-a(1\leq i\leq n)\)，于是\(m\)就需要增加\(\lceil {m\over i}\rceil*(i)-m\)，我们把上取整转化为下取整，\(m\)的增加量就变成了\(\lfloor {m+i-1\over i}\rfloor*i-m=(\lfloor{m-1\over i}\rfloor+1)*i-m\)。于是总花费就是\((\lfloor{m-1\over i}\rfloor+1)*i-m+n-i=\lfloor{m-1\over i}\rfloor*i-m+n\)，而\(n-m\)是一个定值，所以我们只需要知道\(\lfloor{m-1\over i}\rfloor*i\)的最小值即可，而这个可以用整除分块来做，于是问题就被解决了。

代码

#include
using namespace std;
int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>=m){printf("%d\n",n-m);continue;}
        int minn=1000000000;
        for(int i=1;i<=n;i++)
        {
            minn=min(minn,(m-1)/i*i);
            i=(m-1)/((m-1)/i);
        }
        printf("%d\n",n-m+minn);
    }
    return 0;
}