USACO/fence9

分析

方法一：皮克定理

可以算是一道数学题吧。如果知道皮克定理就行了。皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：S = a + b/2 - 1。

根据三角形面积公式求出S。如果知道了b，那么三角形内部格点数目a也就求出来了。

可以证明，一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。

即b=gcd(n,m)+1. gcd(n,m)为n与m的最大公约数。

代入皮克公式，即可求出a的值.

--CmYkRgB123 18:21 2008年4月19日 (CST)

公式：如果m为0，输出0，否则输出((p*m)/2)+1-(((gcd(n,m)+1)+(gcd(abs(n-p),m)+1)+p-2)/2)（gcd（a,b）为a，b的最大公约数）

//注：这个同学没有注意数据范围0<m<32000，所以m≠0啊——whx

---

我想写一下我自己推的式子。。 我花了两个小时才推出来的。。 为了简单好理解，我分步解释一下哈。。（n,m,p是题中的意思，没变）。 首先说一下基本函数：change，就是将a/b约分成最简形式，保存分母b的值（这个挺好写的，就不写出来了）； 可以先分类(其实基本思想是一样的） 1.n=0

｛【(p+1)*(m+1)-(p div change(m,p))+1）】 div 2｝-【m+（p-1）】；（括号都一样，你懂的）  

(p+1)*(m+1)是方格总数，（p div change(m,p))+1是电线过的点数(这个是最重要也是比较不好理解的，最后面给证明） +1的意思是算上过x轴的那个。 前面是将这块看成矩形的，div 2就是分开了。 就是：矩形的一半而且不算电线过的点。 m和p-1都是去掉电线那，画下图就好理解了。 2.n<>0（相信第一个看懂了后面就好说了，直接写式子了）

（1） p>n;
     （（(n+1)*(m+1)-（(n div change(m,n))+1）） div 2）+（（(p-n+1)*(m+1)-(（(p-n) div change(m,p-n))+1）） div 2）-（m+（p+1）-2）；
 （2） p=n 分步了要。。①a1:=(n+1)*(m+1);  ②a2:=(n div change(m,n))+1; ③inc(sum,(a1-a2) div 2);
   ④a3:=m;  ⑤a4:=p-1;  ⑥dec(sum,a3+a4);
 （3） P<n  ①a1:=(n+1)*(m+1);②a2:=(n div change(m,n))+1;③inc(sum,(a1-a2) div 2);④a3:=(n-p+1)*(m+1);⑤ a4:=((n-p) div change ⑥(m,n-p))+1;⑦dec(sum,(a3-a4) div 2);⑧a5:=(n-p) div change(m,n-p);⑨ a6:=p-1;⑩dec(sum,a5+a6);

嗯。式子都写完了。 证明一下 坐标（0,0) (x1,y1) 这两个点经过的整数点的个数是 x1 div change(x1,y1)+1(最后那个1是(0,0)）； 因为（0，0） (x1,y1)是整数点，所以根据三角形相似，这个线上坐标x2就一定<=x1,而且连接(0,0)斜率是y1/x1，所以change只是把斜率化简了！ 假设斜率是k。 那么y2=kx2=(y1/x1)*x2.那么y1*x2/x1就要是整数。假设y1/x1化简之后是a/b，那么就是a*x2/b要是整数，因为a化简了，所以x2一定要是b的倍数（1，2，3——n，0最后算） n最大是多少呢，当然是x1 div (a/b)了！ -by 某蒟蒻

方法二：局部枚举

结果等于(线段(0, 0)--(N, M)与线段(N, M)--(P, 0) )与X轴之间的格点数，我们分别计算两条线段与X轴之间的格点数，然后根据N与P的大小关系进行加减计算即可!

在计算线段与X轴之间的格点数时，我们枚举每一个X轴上的坐标,得到对应于该X坐标下的所有格点数。 具体代码请看C++程序。

方法三：解析几何

这应该是最笨的方法、用数学课上学的直线方程做. (0,0)-(n,m)的方程为y=m/n*x 、(n,m)-(p,0)的方程为y=m(i-p)/(n-p).

枚举x轴上0-m和0-p的整数点求对应y值相加减即可.本来想一次AC.程序也不到20行.. 但是却花了三四十分钟修正、原因是有很多特殊情况没有考虑.下面讲一下要考虑的特殊情况：

1.两条直线上的点不能算进来

2.p<n时注意(n,m)那个点不要重复减两次

3.n=0时判(0,0)-(n,m)线上的整数点小心被零除

方法四：二分向量法

此方法不需要什么高端的鲜为人知的数学方法，也不需要修正可恶的解析几何 只用到向量叉积和二分查找就可以AC！O(n*log2N) 枚举x坐标，然后二分y坐标即可刚开始的区间是（0，M)，每次对比（x,y)和(n,m)的叉积（即求的相对方位），如果（x,y)在（n,m)的上方，那么向下二分，否则向上二分，最后的结果是y值最接近向量(n,m)的点，求出这个点就可以知道从这个点到0有几个点

 /\
/  \

/____\这样的图形可以剖分成

 /|      /|
/ |     / |

/S1| + /S2|(翻转) 如果p>=n (S1+S2) 而如果p<n 则是补成直角三角形后再减去多出的部分（S1-S2） ---Michstar czb.hk/yxg michstar.diandian.com

方法五：向量法

从1到m枚举纵坐标i，设合法的点为(x,i)。那么合法的条件是： 一、从源点(0,0)到(x,i)向量(x-0,i-0)与(n-0,m-0)的叉积应该大于0 二、点(n,m)到点(x,i)组成的向量(n-x,m-i)与点(n,m)到点(p,0)组成的向量(n-p,m-0)的叉积应该大于0 根据以上两点，对于一个纵坐标i,它的合法的横坐标的 L=(i*n)/m + 1; R = (n*m-(m-p)*(m-i))/m; 注意：第二个条件化简得 (n*m-(m-p)*(m-i))/m > x 如果 (n*m-(m-p)*(m-i)) % m==0 ，也就是说R刚刚在边界上，那么结果应该是R-1 By Mushroom

参考代码

C++
C
pascal

引用

[1]