2021牛客寒假算法基础集训营2 D.牛牛与整除分块

题目描述

整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。
整除分块基于这样一个数学现象：对于任意正整数 $N$，集合 $S=\left { x:x=\left \lfloor \frac{N}{i} \right \rfloor ,i\in 1,2,3…N \right }$ 的大小总是严格小于 $2 \sqrt N$ 。
例如当 $N=10$ 时 $S={10,5,3,2,1}$，这就使得对于 $\left \lfloor \frac{N}{i} \right \rfloor$ 类型的求和类问题，只要快速枚举 $S$ 集合，就能在 $\sqrt N$ 级别的复杂度内解决问题。

$\left \lfloor \; \; \right \rfloor$ 符号是向下取整符，$\left \lfloor x \right \rfloor$ 表示不大于 $x$ 的最大正整数

牛牛在学习整除分块这一算法后提出了一个新的问题，对于给定正整数 $N,x$，令$S=\left { x:x=\left \lfloor \frac{N}{i} \right \rfloor ,i\in 1,2,3…N \right }$，时 $\left \lfloor \frac{N}{x} \right \rfloor$在 $S$ 中是第几大呢（去重降序排序后第几个）？

输入描述:

第一行输入一个正整数 $T(1 \leq T \leq 10^6)$，表示测试案例的数目，对于每组案例。
一行两个正整数 $N,x(1 \leq x \leq N \leq 10^9)$

输出描述:

对于每个案例，输出一个正整数，即 $\left \lfloor \frac{N}{x} \right \rfloor$ 在集合 $S$ 中降序排第几大。

示例1

输入

1
2
3

2
25 9
1000000000 1000000000

输出

1
2

8
63244

数论+打表~
我一开始直接上分块，但是 $O(T\sqrt n)$ 的复杂度显然不行，所以只能打表找规律~
打表很容易发现 $k\leq \sqrt n$ 时答案就是 $k$，而另一半正好对称，我们可以假设 $\sqrt n$ 为一条对称轴，那么对于所有大于 $\sqrt n$ 的数 $num$，都有 $num+\lfloor \frac{n}{num}\rfloor=2\sqrt n$，注意当 $n$ 为完全平方数的时候，对称轴会往左移一个单位，加一个 $bool$ 变量判断即可，AC代码如下：

#include<bits/stdc++.h>

using namespace std;
int t, n, k;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        int s = sqrt(n);
        printf("%d\n", k <= s ? k : 2 * s - n / k + (s != n / s));
    }
    return 0;
}