首页 > 试题广场 >

honoka和格点三角形

[编程题]honoka和格点三角形

热度指数：49 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

honoka最近在研究三角形计数问题。
她认为，满足以下三个条件的三角形是“好三角形”。
1.三角形的三个顶点均为格点，即横坐标和纵坐标均为整数。
2.三角形的面积为 $1\$ 。
3.三角形至少有一条边和 $x\$ 轴或 $y\$ 轴平行。
honoka想知道，在平面中选取一个大小为 $n\ * m\$ 的矩形格点阵，可以找到多少个不同的“好三角形”？由于答案可能过大，请对 $1000000007 \$ 取模。

输入描述:

两个正整数和

输出描述:

面积为1的格点三角形的数量，对  取模的结果。

示例1

输入

2 3

输出

说明

格点如下：
*  *  *
*  *  *
不妨设左下角坐标为(1,1)，右上角坐标为到(3,2)。
那么三点坐标可选：
（1，1）（1，2）（3，1）
（1，1）（1，2）（3，2）
（1，1）（2，2）（3，1）
（1，1）（3，1）（3，2）
（1，2）（2，1）（3，2）
（1，2）（3，1）（3，2）
所以共有6个。