Electric Fence

描述

In this problem, "lattice points" in the plane are points with integer coordinates.

In order to contain his cows, Farmer John constructs a triangular electric fence by stringing a "hot" wire from the origin (0,0) to a lattice point [n,m] (0<=n<32,000, 0<m<32,000), then to a lattice point on the positive x axis [p,0] (0<p<32,000), and then back to the origin (0,0).

A cow can be placed at each lattice point within the fence without touching the fence (very thin cows). Cows can not be placed on lattice points that the fence touches. How many cows can a given fence hold?

输入

The single input line contains three space-separated integers that denote n, m, and p.

输出

A single line with a single integer that represents the number of cows the specified fence can hold.

样例输入

 7 5 10

样例输出

20

题意如下

在本题中，格点是指横纵坐标皆为整数的点。

为了圈养他的牛，农夫约翰（Farmer John)建造了一个三角形的电网。他从原点（0,0）牵出一根通电的电线，连接格点(n,m)（0<=n<32000,0<m<32000），再连接格点(p,0)（p>0），最后回到原点。

牛可以在不碰到电网的情况下被放到电网内部的每一个格点上（十分瘦的牛）。如果一个格点碰到了电网，牛绝对不可以被放到该格点之上（或许Farmer John会有一些收获）。那么有多少头牛可以被放到农夫约翰的电网中去呢？
题解

因为边界上的点不能放,所以答案=三角形内所有点-边界上的点

三角形内所有点可以通过 皮克定理:

给定顶点坐标均是整点（或正方形格点）的简单多边形，皮克定理说明了其面积S和内部格点数目n、多边形边界上的格点数目s的关系：

边界上的点可以通过最大公约数算出

举例(0,0)到(n,m)中,一共有gcd(n,m)+1个整点在上面(包含两端)

原理就是假如x可以同时整除n和m的话,(n/x,m/x)必定是整点

所以把三条边全算出来就行了,顶点特殊处理一下

#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
signed main()
{
    int n,m,p;
    cin>>n>>m>>p;
    cout<<(m*p)/2-(gcd(n,m)+gcd(abs(n-p),m)+p)/2+1;
}