CF220D.Little Elephant and Triangle

省选/NOI-

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Little Elephant is playing with the Cartesian coordinates' system. Most of all he likes playing with integer points. The Little Elephant defines an integer point as a pair of integers (x; y), such that 0 ≤ x ≤ w and 0 ≤ y ≤ h. Thus, the Little Elephant knows only (w + 1)·(h + 1) distinct integer points.

The Little Elephant wants to paint a triangle with vertexes at integer points, the triangle's area must be a positive integer. For that, he needs to find the number of groups of three points that form such triangle. At that, the order of points in a group matters, that is, the group of three points (0;0), (0;2), (2;2) isn't equal to the group (0;2), (0;0), (2;2).

Help the Little Elephant to find the number of groups of three integer points that form a nondegenerate triangle with integer area.

小象正在玩笛卡尔坐标系。它最喜欢玩的是整点。小象将整点定义为一对整数 (x,y)(x, y),满足 0≤x≤w0 \le x \le w 且 0≤y≤h0 \le y \le h。因此,小象只知道 (w+1)⋅(h+1)(w+1)\cdot(h+1) 个不同的整点。

小象想要绘制一个顶点均为整点的三角形,且该三角形的面积必须为正整数。为此,它需要找出能构成此类三角形的三元点组的数量。注意:点组中点的顺序是重要的,即三元点组 (0,0), (0,2), (2,2)(0,0),\ (0,2),\ (2,2) 与 (0,2), (0,0), (2,2)(0,2),\ (0,0),\ (2,2) 被视为不同。

请帮助小象找出能构成面积为正整数的非退化三角形的整点三元组的数量。

输入格式

A single line contains two integers w and h (1 ≤ w, h ≤ 4000).

一行包含两个整数 ww 和 hh(1 ≤ w, h ≤ 40001 \le w, h \le 4000)。

输出格式

In a single output line print an integer — the remainder of dividing the answer to the problem by 1000000007 (109 + 7).

在单行输出中打印一个整数——即该问题答案对 1000000007(109+710^9 + 7)取模的余数。

输入输出样例

  • 输入#1

    2 1

    输出#1

    36
  • 输入#2

    2 2

    输出#2

    240

输入解题思路,AI测评打分。不知道怎么写?

首页