题目解析

给定正整数 (n, m)，求满足以下条件的有序对 ((a, b)) 的数量：

• (1 \le a \le n,\ 1 \le b \le m)
• (a + b) 是 (b \cdot \gcd(a, b)) 的倍数。

推导过程

设 (d = \gcd(a, b))，并令
[ a = p \cdot d,\quad b = q \cdot d, ]
其中 (\gcd(p, q) = 1)。

条件化为： [ b \cdot \gcd(a, b) = q d^2 \quad \text{整除} \quad a + b = d(p + q), ]
即 [ q d \mid (p + q). ]
因此存在正整数 (k) 使得 [ p + q = k q d \quad\Longrightarrow\quad p = (k d - 1) q. ]

由于 (\gcd(p, q) = 1)，且 (p = (k d - 1) q)，可得 [ \gcd(p, q) = \gcd((k d - 1) q, q) = q \cdot \gcd(k d - 1, 1) = q. ]
所以 (q = 1)，从而 (b = d)，且 [ p = k d - 1,\qquad a = p d = (k d - 1) d. ]

现在 (a) 必须满足 (1 \le a \le n)，即 [ (k d - 1) d \le n \quad\Longrightarrow\quad k d \le \frac{n}{d} + 1 \quad\Longrightarrow\quad k \le \frac{n/d + 1}{d}. ]
由于 (k) 为正整数，其最大值为 [ k_{\max} = \left\lfloor \frac{\lfloor n/d \rfloor + 1}{d} \right\rfloor, ]
这里用 (\lfloor n/d \rfloor) 代替 (n/d) 是为了保持整数运算。

对于固定的 (d)，所有满足条件的 (a) 对应于 (k = 1, 2, \dots, k_{\max})。
注意当 (d = 1) 且 (k = 1) 时，(a = (1\cdot1 - 1)\cdot1 = 0)，不满足 (a \ge 1)，因此这一对应该被排除。而其他所有 (k) 都给出合法的 (a)。

因此，对每个 (d)（(1 \le d \le m)，因为 (b = d \le m)），合法 ((a, b)) 的数量为 (\left\lfloor \frac{\lfloor n/d \rfloor + 1}{d} \right\rfloor)，但需要从总和中减去 (d = 1, k = 1) 这一多余情况。

于是最终答案为： [ \text{ans} = \left( \sum_{d=1}^{m} \left\lfloor \frac{\lfloor n/d \rfloor + 1}{d} \right\rfloor \right) - 1. ]

时间复杂度

直接枚举 (d = 1 \to m) 即可，单次复杂度 (O(m))。由于所有测试用例的 (m) 之和不超过 (2\cdot10^6)，总复杂度可以接受。

代码实现（示意）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000005;
int tc,n,m; ll ans;
inline void solve(){
	cin>>n>>m; ans=0;
	for(int i=1;i<=m;i++)
		ans+=(n+i)/(1ll*i*i);
	cout<<ans-1<<'\n';
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>tc; while(tc--) solve();
	return 0;
}