CF1370A Maximum GCD

我们考虑区间 $1$ 到 $n$（包含 $n$）内的所有整数。 在所有区间内不同整数对中，找出它们的最大公约数的最大值。形式化地说，求所有满足 $1 \leq a < b \leq n$ 的整数对 $(a, b)$ 中，$\mathrm{gcd}(a, b)$ 的最大值。 两个正整数 $a$ 和 $b$ 的最大公约数 $\mathrm{gcd}(a, b)$ 是同时整除 $a$ 和 $b$ 的最大整数。

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例仅包含一行，一个整数 $n$（$2 \leq n \leq 10^6$）。

对于每个测试用例，输出在所有满足 $1 \leq a < b \leq n$ 的整数对中，$\mathrm{gcd}(a, b)$ 的最大值。

在第一个测试用例中，$\mathrm{gcd}(1, 2) = \mathrm{gcd}(2, 3) = \mathrm{gcd}(1, 3) = 1$。 在第二个测试用例中，最大可能值为 $2$，对应于 $\mathrm{gcd}(2, 4)$。 由 ChatGPT 4.1 翻译