RT，给定 $a_1,a_2,\dots,a_n$，求自然数序列 $x_1,x_2,\dots,x_n$，使得 $\sum_{i=1}^{n}(a_ix_i)\equiv 0(\bmod p)$，并且 $\sum_{i=1}^{n}a_i$ 最小。如有多个满足条件的序列则输出字典序最小的。

有复杂度低于 $O(n\log(\prod_{i=1}^{n}a_i))$ 的解法吗？

说是关于拓欧仅仅是个人感觉