题目描述
在本题中，格点是指横纵坐标皆为整数的点。
为了圈养他的牛，农夫约翰（Farmer John)建造了一个三角形的电网。他从原点（0,0）牵出一根通电的电线，连接格点(n,m)（0<=n<32000,0<m<32000），再连接格点(p,0)（p>0），最后回到原点。
牛可以在不碰到电网的情况下被放到电网内部的每一个格点上（十分瘦的牛）。如果一个格点碰到了电网，牛绝对不可以被放到该格点之上（或许Farmer John会有一些收获）。那么有多少头牛可以被放到农夫约翰的电网中去呢？
输入格式
输入文件只有一行，包含三个用空格隔开的整数：n,m和p。
输出格式
输出文件只有一行，包含一个整数，代表能被指定的电网包含的牛的数目。
输入输出样例
7 5 10
20
说明/提示
题目翻译来自NOCOW。
USACO Training Section 3.4
#include#include #include #include #include #include using namespace std;long long n,m,p;long long read(){ long long a=0,b=1; char ch=getchar(); while((ch<48||ch>57)&&ch!='-'){ ch=getchar(); } if(ch=='-'){ b=-1; ch=getchar(); } while(ch<48||ch>57){ ch=getchar(); } while(ch>47&&ch<58){ a=a*10+ch-48; ch=getchar(); } return a*b;}long long gcd(long long x,long long y){ return x%y==0?y:gcd(y,x%y);}int main(){ n=read(),m=read(),p=read(); long long s=p*m/2; long long cnt=(gcd(n,m)+gcd(abs(n-p),m)+p)/2; long long ans=s-cnt+1; printf("%lld\n",ans); return 0;}
广告：
了解一下。
发现者
姓名:乔治·亚历山大·皮克(1859~1943)
全名:George Alexander Pick
国籍:奥地利
概括
皮克定理是指一个计算中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。
定理定义
一张方格纸上，上面画着两组，相邻平行线之间的距离都相等，这样两组平行线的交点，就是所谓。如果取一个格点做原点O，如图1，取通过这个格点的和两直线分别做轴OX和纵坐标轴OY，并取原来方格做长，建立一个坐标系。这时前面所说的格点，显然就是纵横两都是整数的那些点。如图1中的O、P、Q、M、N都是格点。由于这个，我们又叫格点为。
一个的顶点如果全是格点，这多边形就叫做格点多边形。有趣的是，这种格点多边形的面积计算起来很方便，只要数一下图形上的点的及图内的点的数目，就可用公式算出。
这个公式是皮克(Pick)在1899年给出的，被称为"皮克定理"，这是一个而有趣的定理。
给定顶点坐标均是整点(或正方形格点)的简单多边形，皮克定理说明了其面积S和内部格点数目n、边上格点数目s的关系:
(其中n表示多边形的点数,s表示多边形上的,S表示多边形的面积)
验证推导
因为所有简单多边形都可为一个三角形和另一个简单多边形。一个简单多边形P，及跟P有一条共同边的三角形T。若P符合皮克公式，则只要P加上T的PT亦符合皮克公式(I)，以及三角形皮克公式(II)，就可根据数学归纳法，对于所有简单多边形皮克公式都是的。
多边形
设P和T的共同边上有c个格点。
P的面积: iP + bP/2 - 1
T的面积: iT + bT/2 - 1
PT的面积:
(iT + iP + c - 2) + (bT- c + 2 + bP - c) /2 - 1 = iPT + bPT/2 - 1
三角形
证明分三部分:证明以下的图形符合皮克定理:
所有平行于的矩形;
以上述矩形的两条邻边和对角线组成的直角三角形;
所有三角形(因为它们都可内接于矩形内，将矩形分割成原三角形和至多3个第二点提到的直角三角形)。
矩形
设矩形R长边短边各有m,n个格点:
AR = (m-1)(n-1)
iR = (m-2)(n-2)
bR = 2(m+n)-4
iR + bR/2 - 1 = (m-2)(n-2) + (m+n) - 2 - 1 = mn - (m + n) +1 = (m-1)(n-1)
直角三角形
易见两条邻边和组成的两个直角三角形全等，且i,b相等。设其斜边上有c个格点。
b = m+n+c-3
i = ((m-2)(n-2) - c + 2)/2
i + b/2 - 1 = ((m-2)(n-2) - c + 2)/2 + (m+n+c-3)/2 - 1 = (m-2)(n-2)/2 + (m+n - 3)/2 = (m-1)(n-1)/2
一般三角形
逆运用前面对2个多边形的证明: 既然矩形符合皮克定理，直角三角形符合皮克定理。又前面证明到若P，T符合皮克公式，则 P加上T的PT亦符合皮克公式。 那么由于矩形可以分解成1个任意三角形和至多三个直角三角形。 于是显然有，只有当这个任意三角形也符合皮克定理的时候，才会使得在直角三角形符合的同时，矩形也符合。