今天的组队赛有一道不停TLE的题，现在来补题，顺便写题解做记录。

原题链接

总结：数论知识匮乏，需要补充的知识：整除分块、上取整与下取整的互相转化。

题意：给定多组n,m，有两种操作：n-1，m+1，问至少操作多少次可以使得m%n==0.

推导过程：

n>=m时明显至少需要(n-m)次操作，重点在于m>n的情况。

此时假设n减小了a，则m需要增加到，由于m变大后必须为n-a的倍数，这里的上取整能让m增加最少数量的(n-a)。

此时设i=n-a，可以表示出需要操作的次数为.

由上下取整转化公式（n、m均为整数）可得原式，注意常数可以从取整符号中拆出来，不会影响整个式子的值。

接下来只需考虑如何得到的最小值。

需要引入一个重要方法：整除分块，能够大幅减少枚举量，本质上就是跳过整除值相等的部分，在本题中用在寻找的最小值上，避免无用的计算，减少计算时间。

找到最小值后带回原式输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,t;

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(n>=m){
            printf("%d\n",n-m);
            continue;
        }
        int mi=1e9;
        for(int i=1;i<=n;i++){
            mi=min(mi,(m-1)/i*i);
            i=(m-1)/((m-1)/i);
        }
        printf("%d\n",mi+n-m);
    }
    return 0;
}