简要题意
给定一个 \(n \times n\) 矩阵，矩阵中的每一个元素的计算方式如下：
- 随机从 \([0, n - 1]\) 中选出两个整数（可以重复）\(a, b\)，矩阵的元素为 \(a \times b \bmod n\)
求矩阵中元素 \(m\) 出现次数的期望。
- \(0 \le m < n \le 10^{12}\)
题解
对于矩阵中的任意一个元素是独立的，因此我们考虑对于一组 \(a \times b \equiv m \pmod n\) 的期望。
原式可推出 \(ab + kn = m\)，由裴蜀定理可知，当 \(\gcd(a, n) \mid m\) 时，方程有线性解。
接下来考虑对于一个合法的 \(a\) 有多少组解是可以被接受的，由于 \(at = sn\)，我们想要找到尽可能小的 \((s, t)\) 的一组解，那么 \(t = \frac{n}{\gcd(a, n)}\)，若 \(ab \equiv m \pmod n\)，那么 \(a\left(b + \frac{n}{\gcd(a, n)}\right) \equiv m \pmod n\)。
考虑将 \(m\) 分解，必存在最小的二元组 \((a, b)\) 使得同余式成立，因此所有的合法解为：
\[\sum_{d \mid m}\frac{n - \frac{m}{d}}{\gcd(d, n)} \] 标签：frac,gcd,pmod,矩阵,BUPT,Programming,times,2024,equiv From： https://www.cnblogs.com/YipChipqwq/p/18491756