关于一道高斯函数题目
Published:
令 $\lfloor x \rfloor$ 为不大于 $x$ 的最大整数。${x} = x - \lfloor x \rfloor$。
题目 1
题面
求值：
\[\sum\limits_{i=1}^{2015} \left\{\frac {2015 i} {2016} \right\}\]标准答案
\[\begin{aligned} & \left\{\frac {2015 i} {2016} \right\} \\ =& \left\{\frac {(2016-1) i} {2016} \right\} \\ =& \left\{\frac {-i} {2016} \right\} \\ =& 1 - \frac i {2016} \end{aligned}\]对这个求和就没有难度了。答案为 $\boxed{\frac {2015} 2}$。
题目 2
求值：
\[\sum\limits_{i=1}^{2015} \left\{\frac {2011 i} {2016} \right\}\]尝试使用上文的方法
\[\begin{aligned} & \left\{\frac {2011 i} {2016} \right\} \\ =& \left\{\frac {(2016-5) i} {2016} \right\} \\ =& \left\{\frac {-5i} {2016} \right\} \\ \end{aligned}\]好了不会了。
使用数论！
\[\begin{aligned} & \left\{\frac {2011 i} {2016} \right\} \\ =& \frac 1 {2016} (2011i \bmod 2016) \\ \end{aligned}\]引理 1
若 $a \perp m$ 且 $ax \equiv ay \pmod m$，则 $x \equiv y \pmod m$。
证明：$a(x-y) \equiv 0 \pmod m$，因此 $x-y \equiv 0 \pmod m$。
继续推导
\[\begin{aligned} & \sum\limits_{i=1}^{2015} \left\{\frac {2011 i} {2016} \right\} \\ =& \frac 1 {2016} \sum\limits_{i=1}^{2015} (2011i \bmod 2016) \\ =& \frac 1 {2016} \sum\limits_{i=1}^{2015} i & \text{引理 1} \\ =& \boxed{\frac {2015} 2} \end{aligned}\]
题目 3
求值：（$a,m$ 均为正整数）
\[\sum\limits_{i=1}^{m} \left\{\frac {a \times i} m \right\}\]使用数论！
引理 2
若 $ax \equiv ay \pmod m$，则 $x \equiv y \pmod {\frac m {\gcd(a,m)}}$。
证明：两边同除 $\frac a {\gcd(a,m)}$ 后显然。
继续推导
\[\begin{aligned} & \sum\limits_{i=1}^m \left\{\frac {a \times i} m \right\} \\ =& \frac 1 m \sum\limits_{i=1}^m (ai \bmod m) \\ =& \frac 1 m \gcd(a,m)^2 \sum\limits_{i=1}^{\frac m {\gcd(a,m)}-1} i & \text{引理 2} \\ =& \boxed{\frac {m - \gcd(a,m)} 2} \end{aligned}\]另一种方法：皮克定理
原式即为：
\[\sum\limits_{i=1}^m \frac {a \times i} m - \sum\limits_{i=1}^m \left\lfloor \frac {a \times i} m \right\rfloor\]而 $\sum\limits_{i=1}^m \left\lfloor \frac {a \times i} m \right\rfloor$ 即为 $y = \frac a m x$ 上及其下方的整点个数。使用皮克定理：
\[I = A - \dfrac B 2 + 1\] \[\sum\limits_{i=1}^m \left\lfloor \frac {a \times i} m \right\rfloor - \gcd(a,m) - a + 1 = \frac {am} 2 - \frac{m + a + \gcd(a,m)} 2 + 1\] \[\sum\limits_{i=1}^m \left\lfloor \frac {a \times i} m \right\rfloor = \frac {am + a - m + \gcd(a,m)} 2\]化简可得：
\[\sum\limits_{i=1}^m \left\{\frac {a \times i} m \right\} = \boxed{\frac {m - \gcd(a,m)} 2}\]总结
- 遇到高斯函数与分数的相关问题，可以考虑数论中的 $\bmod$ 运算。
- 利用高斯函数的几何意义，将求和问题改为数整点问题，利用皮克定理求解。
参考
[Pick定理的几个出人意料的应用 Matrix67: The Aha Moments](http://www.matrix67.com/blog/archives/2199) - 我自己的 Pick’s Theorem 学习笔记
- sequences and series - floor number sum - Mathematics Stack Exchange