题解：P11184 带余除法

注意到当 $q$ 确定时 $r$ 也能随之唯一确定。因此问题变成了求有多少合法 $q$。

何为合法？$\left \lfloor \dfrac nq\right \rfloor = k$。

显然合法的 $q$ 是连续的。因此我们可以二分出 $q$ 的最小和最大取值 $q_{\min},q_{\max}$。那么 $q_{\max}-q_{\min}+1$ 即为答案。

注意需要特判：

- $b=0$：输出 $1$；
- $b > a$：输出 $0$。

```cpp
// Problem: U480670 带余除法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/U480670?contestId=200686
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long ll;

signed main() {
	int T;
	cin >> T;
	while (T -- ) {
		ll a, b;
		cin >> a >> b;
		if (b > a) cout << 0 << '\n';
		else if (!b) cout << 1 << '\n';
		else {
			ll lo = 1, hi = 1e14, L = 2, R = 1;
			
			while (lo <= hi) {
				ll mid = lo + hi >> 1;
				if (a / mid <= b) {
					L = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			
			lo = 1, hi = 1e14;
			while (lo <= hi) {
				ll mid = lo + hi >> 1;
				if (a / mid >= b) {
					R = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
			
			cout << max(0ll, R - L + 1) << '\n';
		}
	}
	return 0;
}
```

正在渲染内容...