例题1

求和：
<!–swig0–>

方法1

首先令$m = \left\lfloor {\sqrt k } \right\rfloor $
那么有
<!–swig2–>
我们先算左半部分，先假设$n = {a^2}$，那么有
<!–swig4–>
而对于一般的$n$，令$a = \left\lfloor {\sqrt n } \right\rfloor $，我们只需要计算${a^2} \le k < n$的部分，而这部分$\sqrt k = a$，所以结果为$(n - {a^2})a$。

所以总的结果为：
<!–swig10–>

这里解释一下为什么没有算右半部分？因为右半部分就是${a^2} \le k < n$的这部分，已经计算过了。

方法2

因为$\left\lfloor x \right\rfloor = \sum\nolimits_j {\left[ {1 \le j \le x} \right]} $，所以可以将原式替换掉，还是令$n = {a^2}$，然后如下计算：
<!–swig14–>
其中第二行交换了变量计算顺序。

定理1

这里直接介绍一个定理，就不证明了，过程比较复杂：
<!–swig15–>
其中$\alpha $是一个无理数。

这个公式说明了，无理数$\alpha $的整数倍的小数部分均匀分布在$(0,1)$之间。

这就给了我们一个启示，我们可以用它来生成随机数啊！其他用处还有很多，自己想咯。

例题2

求如下和式：
<!–swig19–>
其中整数$m > 0$，$n$也是整数。

通过枚举$m = 1,2,3, \ldots $，可以发现和式满足如下形式：
<!–swig23–>
那么怎么计算出来呢？

首先做一个变形：
<!–swig24–>
这就将原来的和式分为了三个部分求和。

第一个部分为：
<!–swig25–>
具体怎么算留到下一章节，这里通过枚举可以发现它的值是有周期的，周期重复次数是$d = \gcd (m,n)$。所以算出来结果为：
<!–swig27–>
第二个部分为：
<!–swig28–>
第三个部分为：
<!–swig29–>

所以总的结果为：
<!–swig30–>

这里我们对结果稍稍变形，可以得到另一个结果：
<!–swig31–>
可以发现，$m$和$n$是对称的！所以可以得到如下结论：
<!–swig34–>
这有什么用呢？当$m$特别大、$n$很小的时候可以大大减少项的个数！

如果我们令$n=1$，就会发现，得到的式子和之前证过的一个式子一模一样！
<!–swig38–>

到这里为止，第三章取整就讲完了，下面开始讲第四章数论部分。

数论相关性质

整除定义

<!–swig39–>
注意这里整除的定义中要求$m>0$。

最大公约数和最小公倍数

定义我就不说了，大家应该都知道的。

欧几里得定理

又叫辗转相除法，就是用来求最大公约数的。
<!–swig41–>

扩展欧几里得定理

在用欧几里得定理求到最大公约数之后，反过来可以将最大公约数表示为两个数的线性和：
<!–swig42–>

性质1

如果$k|m,k|n$，那么$k|gcd(m,n)$。

性质2

<!–swig45–>
这个就是用了交换律，按照因子顺序倒过来算。

性质3

<!–swig46–>
这个虽然变成了二重求和，但是对于每个$k$，其实只有一个$m$有效。

性质4

<!–swig49–>
这个一眼就不一定能看出来了。

左边等于：
<!–swig50–>
右边等于：
<!–swig51–>
可以看出左右两边相等。

算数基本定理

一个整数可以唯一表示为若干个素数乘积：
<!–swig52–>
所以用指数形式来表示一个整数$n$，例如$18 = {2^1} \times {3^2}$，那么$18$可以表示为：
<!–swig56–>
最大公约数和最小公倍数也能很方便的用指数形式计算：
其中最大公约数的每个素数的指数等于两个数对应指数最小值，最小公倍数的每个素数的指数等于两个数对应指数最大值。