• 时间限制 $1s$，$n \leq 10^7$。请问值域开到多少可以卡掉基数排序？

• 例如有这么一个问题：

给定一个序列 $a$，将 $a$ 从小到大排序。

$n \leq 10^7,a_i \leq 10^9$。

我自己想了一个奇怪的排序方法：

选择一个数 $k$，例如 $k=5 \times 10^3$。对于每一个数，都算出这个数除以 $k$ 得到的商和余数。那么显然，商的值不会大于 $2 \times 10^5$，余数的值不会大于 $5 \times 10^3$。首先我先按照商从小到大，这个用桶排。然后对于商相等的数，再用桶以余数从小到大排序。那么最终的序列就是商乘以 $k$ 加上余数。

所以我那个思路可以吗？我觉得如果这个思路可行，那么对于 $n \leq 10^7,a_i \leq 10^{12}$ 都可以使用 $O(n)$ 排序（$k$ 取 $10^6$）。