高中时代学习 OI 的时候，我就曾经思考过，能不能把费马小定理推广到模意义下的矩阵。
就是说对于质数 $p$ 和矩阵 $A \in \mathbb Z_p^2$，如果 $A$ 可逆，能不能找到一个 $\phi = \phi(n, p)$ 使得 $A^\phi \equiv E_n \pmod p$。
高中时代的我没能解决这个问题，然后就把它忘了。
现在，大四的某一天，我突然回想起了这个问题。
我跑去问 ChatGPT，结果它啪的一下就给我回答出来了。
答案就是
$$|GL(n, \mathbb Z_p)| = \prod_{k = 0}^{n - 1} (p^n - p^k)$$
感受到了群论的力量……
考虑一下，这样我们就设计出了一个全新的模意义下求逆矩阵的算法。它的时间复杂度是……
$$\Theta \left( n^3 \log_2 \prod_{k = 0}^{n - 1} (p^n - p^k) \right) = \Theta \left( n^5 \log p \right)$$
被高消暴打……
Comments NOTHING