[CQOI2014]数三角形

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题号 NC19934
名称 [CQOI2014]数三角形
来源 [CQOI2014]

题目描述

给定一个 n×m的网格，请计算三点都在格点上的三角形共有多少个。

注意：三角形的三点不能共线。

样例

输入：
2 2
输出：
76

算法1

(容斥原理 + 组合计数)

三个点确定一个三角形，我们求出从 $(n + 1) * (m +1)$ 个点中选择三个点的组合数 - 三点构成直线的数量（容斥原理）

图片说明

如上图：任意一条两个端点在整点上的线段，其覆盖的整点数量为 $gcd(l,r) + 1$

对于不同长度线段（两个端点在整点上）都对应到一个长 $l$ 或高 $h$ 不同的直角三角形
对于定长的线段我们可以通过将两个点固定在线段的两个端点，另一个点从中间的点中选来得到，方案数就为 $gcd(l,r) + 1 - 2 = gcd(l,r) - 1$
除了长度不同，我们还可以通过平移来得到不同的线段
斜率为正的线段和斜率为负的线段个数是相等的

用 $res$ 记录去掉水平和铅锤线段的方案数

然后我们用 $O(n * m)$ 的循环枚举直角三角形的直角边长 $i,j$ ，计算直角三角形对应线段的方案的个数 $s_{i,j}$

答案就为 $res - \sum_{i=1}^{n}\sum_{j=1}^{m}s_{i,j}$

时间复杂度 $O(n * m * logn)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int n,m;

LL C(int a)
{
    return 1ll * a * (a - 1) * (a - 2) / 6;
}

int main()
{
    scanf("%d%d",&n,&m);
    n ++,m ++;//点的数量是长度 + 1
    LL res = C(n * m) - n * C(m) - m * C(n);//总方案数减去水平的线段和铅锤的线段
    for(int i = 1;i < n;i ++)
        for(int j = 1;j < m;j ++)
            res -= 2ll * (__gcd(i,j) - 1) * (n - i) * (m - j);
            //减去不同长度的线段的方案数,* 2是计算不同斜率的线段，* (n - i) * (m - j)计算平移后的直线段个数
    printf("%lld\n",res);
    return 0;
}