题目
平均来说，一个正整数\(n\)能被写成两个整数平方和的有序对\((i,j)\)的方式有多少种？换句话说，\(n\)在\(1\)到极大值中随机取，期望有多少组\((i,j)\)满足\(n=i^2+j^2\)？
分析
关键思路
- 固定\(n\)，\((i,j)\)满足\(n=i^2+j^2\)，等价于点\((i,j)\)落在以原点为中心、半径\(\sqrt{n}\)的整点圆上。
- 问题转化为：\(1\leq n\leq N\)，平均每个\(n\)有多少组\((i,j)\)满足\(n=i^2+j^2\)。
- 记\(S(N)\)为\(1\leq n\leq N\)，所有满足\(n=i^2+j^2\)的有序对\((i,j)\)的总数。
- 期望值\(E=\frac{S(N)}{N}\)。
但\(S(N)\)也等于所有\(|i|,|j|\leq\sqrt{N}\)，\(n=i^2+j^2\leq N\)的点的个数。
- 换句话说，\(S(N)\)等于以原点为中心、半径\(\sqrt{N}\)的整点点数对\((i,j)\)的个数。
对于每个\((i,j)\)，\(n=i^2+j^2\)，\(n\)在\(1\)到\(N\)之间，则\((i,j)\)落在以原点为中心、半径\(\sqrt{N}\)的整点点。
- 共有多少个这样的\((i,j)\)？就是圆内整点个数，约为\(\pi N\)（高斯圆点计数定理）。
所以\(S(N)\sim \pi N\)，于是期望\(E\sim \pi\)。
结论
当\(N\)很大时，平均每个\(n\)能被写成两个整数平方和的有序对\((i,j)\)的方式约为\(\pi\)。