基础计算机和-Pick定理

Pick定理内容

设二维平面上只有整数点，多边形的面积为S，多边形包含的点个个数为a，多边形边上的点的个数为b，则有以下等式

$$S=a+\frac{b}{2}-1$$

Pro:证明过程

Pick定理的扩展-Farey序列

Fatey序列是指那些0-1之间且分母不超过n的分数从小到大，例如

$$F_5=\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}$$

把每个分数等价于一个二维平面上的坐标点就可以得到，例如$\frac{0}{1}=(1,0)$，就可以得到下面这个图

这张图假设一条射线从x正向出发，逆时针扫向y轴正向，就能够得到我们的Farey序列。并且，相邻两个扫描过的点与原点组成的三角形的面积切好为$\frac{1}{2}$,这是因为因为Farey序列的分数都是最简分数，所以他们之间并没有公因子，因此他们的内部就不存在公共点，所以面积的计算为$S=\frac{3}{2}-1=\frac{1}{2}$，因为两个点之间的面积为叉积的一半，所以得到(m,n),(p,q)，

$$\begin{aligned} &\frac{(mq-np)}{2}=\frac{1}{2}\\ &(mq-np)=1\\ &mq=np+1 \end{aligned}$$