526互联

tzoj5103 Electric Fence 电网

发布时间 2023-08-12 19:26:27作者: Yosuganosora

题目大意

给定三个正整数n，m和p，将(0,0) (n,m) (0,p) 这三个点相连，求围成的三角形中的格点数目(三角形边上的格点不算)

利用皮克定理求出。

皮克定理

顶点全在格点上的多边形面积S=n+T/2-1。

n为多边形内部格点数量，T为多边形边上的格点数量。

解题方法

内部格点数量n=S-T/2+1。

三角形面积S直接用面积公式求出。三角形底边格点数量为P+1，另外两条边上的格点数量用为gcd(n,m)+1和gcd(abs(n-p),m)+1，再减去重复的三个顶点，求出T。

代码

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

// S-T/2+1=n
// S=p*m/2
// T=p+1+gcd(n,m)+1+gcd(m, abs(n-p))+1-3;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
signed main()
{
    IO;
    int n, m, p;
    cin >> n >> m >> p;
    cout << p * m / 2 - (gcd(n, m) + p + gcd(m, abs(n - p))) / 2 + 1 << endl;
    return 0;
}