#P3166. 网格数三角形(Counting Triangles)
0
网格数三角形(Counting Triangles)
网格数三角形(Counting Triangles)
题目描述
给定一个 的网格,请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。
输入格式
输入一行,包含两个空格分隔的正整数 和 。
输出格式
输出一个正整数,为所求三角形数量。
样例输入 #1
2 2
样例输出 #1
76
数据范围
数据规模与约定
对于全部的测试点,保证 。
知识点与难度
本题涉及的知识点从属于 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 格点共线容斥测试 |
出处:原题链接