题目链接

题意

给定一个格点三角形，三个顶点分别为(0,0),(n,m),(p,0)，求三角形内部的格点个数。

思路

皮克公式：

\[S = \frac{i}{2}+b-1
\]

\(S\)为三角形面积，\(i\)为三角形边界上的格点个数，\(b\)为三角形内部的格点个数。

\(i\)可由\(gcd\)求得。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int gcd(int a, int b) {

    return b ? gcd(b, a % b) : a;

}

int main() {

    int n, m, p;

    scanf("%d%d%d", &n, &m, &p);

    int i = gcd(n, m) + gcd(abs(p-n), m) + p;

    LL b = (1LL * p * m - i) / 2 + 1;

    printf("%lld\n", b);

    return 0;

}

巴特西

luogu 2735 电网皮克公式

题目链接

题意

思路

Code

最新文章

热门文章

巴特西

luogu 2735 电网 皮克公式

题目链接

题意

思路

Code

最新文章

热门文章

luogu 2735 电网皮克公式