三角形

题目描述

小 J 是一名 OI 退役滚粗文化课选手, 他十分喜欢做题, 尤其是裸题. 下面就送大家一道裸题. 给定一张 \(N \times M\) 的网格, 计算三个点都在网格上的三角形有多少个. 三角形三点不 能共线.

输入格式

一行两个正整数 N, M.

输出格式

一行一个整数代表数量.

样例输入

1 1

样例输出

4

数据范围

对于 10% 的数据有 \(N, M \leq 10\)

对于 30% 的数据有 \(N, M \leq 100\)

对于 100% 的数据有 \(N, M \leq 1000\)

Explanation

枚举所有的直线斜率, 并不考虑斜率的 \(x\) 和 \(y\) 互质的情况. 进而, 这个操作的时间复杂度明显是 \(O(n m)\) 的.

在这个过程之后, 我们可以得知将一条线段可以拆成几种情况. 这几个拆的位置必须在格点 上. 所以拆的位置只有 \(gcd(n, m)\) 种.

然而总的复杂度的确是 \(O(n m)\) 的.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

lli gcd(lli a, lli b)
{
    while (b != 0) {
        lli c = a % b;
        a = b;
        b = c;
    }
    return a;
}

lli n, m;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &m);
    n++, m++;
    lli tot = (n * m) * (n * m - 1) * (n * m - 2) / 6;
    for (lli i = 1; i <= n; i++)
        for (lli j = 1; j <= m; j++) {
            lli g = 1;
            lli tmp;
            if (i == 1) {
                g = j - 1;
                if (g <= 1)
                    continue;
                tmp = g - 1;
                tmp *= n * (m + 1 - j);
                tot -= tmp;
            } else if (j == 1) {
                g = i - 1;
                if (g <= 1)
                    continue;
                tmp = g - 1;
                tmp *= m * (n + 1 - i);
                tot -= tmp;
            } else {
                g = gcd(i - 1, j - 1);
                if (g <= 1)
                    continue;
                tmp = g - 1;
                tmp *= (n + 1 - i) * (m + 1 - j);
                tmp *= 2;
                tot -= tmp;
            }
            // printf("%d %d %d %d\n", i, j, g, tmp);
        }
    printf("%lld\n", tot);
    return 0;
}