#P3166. 网格数三角形(Counting Triangles)

0
    ID: 8620 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>P3166组合数学容斥原理最大公约数CSP-S

网格数三角形(Counting Triangles)

网格数三角形(Counting Triangles)

题目描述

给定一个 N×MN\times M 的网格,请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

输入格式

输入一行,包含两个空格分隔的正整数 MM 和 NN。

输出格式

输出一个正整数,为所求三角形数量。

样例输入 #1

2 2

样例输出 #1

76

数据范围

数据规模与约定

对于全部的测试点,保证 1≤N,M≤10001\le N,M\le1000。

知识点与难度

本题涉及的知识点从属于 CSP-S,难度(CF Rating):1700。


测试点分布

Subtask 分值 测试点编号 说明
0 10 1 样例
1 25 2~8 小规模 N,M≤20 / 特殊: N=1, M=1
2 30 9~16 中等规模 N,M≤200
3 35 17~25 满规模 N,M≤1000 格点共线容斥测试

出处:原题链接