引言

题目链接：https://codeforces.com/contest/1925/problem/B

思路

由于最后的答案是 x 分解的全部数的 gcd，所以该答案一定是 x 的因数，只要遍历 x 的因数 k，那么该因数能将 x 分解成 \(\frac{x}{k}\) 份。

若 \(\frac{x}{k} \geq n\)，则可将其构造成 n 组，gcd 为 k 的答案，只需要找到这些答案中的最大值即可。

代码

#include <bits/stdc++.h>

void solve() {
	int x,n;
	std::cin >> x >> n;

	int ans = 1;
	for (int i = 1 ; i * i <= x ; i ++ ) {
		if(x % i == 0) {
			if(x / i >= n) ans = std::max(ans,i);
			if(i >= n) ans = std::max(ans, x / i);
		}
	}
	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t;
	std::cin >> t;
	while(t -- ) {
		solve();
	}
	return 0;
}