Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

01/2
19:50
组合数/lucas

Cqoi2014 数三角形 [bzoj 3505]

00:00/00:00

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

76

数据范围
1<=m,n<=1000

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

先从n*m个点中任意选3个,然后减去三点共线的,可以分成三种情况:同一行,同一列,同一斜线。写线上的点可以用gcd来搞。

c++:

 

pascal:

 

Cqoi2014 数三角形 [bzoj 3505]