数三角形

发表于 | 更新于
本文字数： 2.7k | 阅读时长 ≈ 2 分钟

$Counting$ $Delta$

$Description$

给定一个 $n \times m$ 的网格，请计算三点都在格点上的三角形共有多少个。

$Solution$

考虑分类讨论。

首先，我们发现，每个顶点都在格点上的三角形能且只能被一个矩形完全包含，也就是

而下面这个当中的大矩形就是不包含这个下图中的三角形的，只有用红色标出的小矩形才包含。

所以就将问题转化成了求子矩形个数。

显然，长为 $i$ ，宽为 $j$ 的子矩形有 $(m - i + 1) \times (n - j + 1)$ 个。

然后考虑一个子矩形中有多少种可能的三角形个数。

我们考虑固定一个端点，移动其他两个端点：

红色的点表示固定的点，也就是 $A$ 点，绿色的线表示 $B$ 点此时的活动范围，橙色的线表示 $C$ 点此时的活动范围。

显然， $A​$ 点有 $4​$ 种方案， $B​$ 点有 $i - 1​$ 种方案， $C​$ 点有 $j - 1​$ 种方案。

所以方案数就是 $4 \times (i - 1) \times (j - 1)​$

然后我们考虑处在顶点上的特殊情况，我们钦定 $B$ 与顶点重合。

当 $B$ 与左上角端点重合时， $C$ 就只能在右边的一条边上动，就有 $i - 1$ 种情况。

当 $B$ 与右下角端点重合时， $C$ 就只能在上面的一条边上动，就有 $j - 1$ 种情况。

当 $B​$ 与右上角端点重合时，情况就变得复杂了。

可以发现此时 $A \to B$ 不仅仅经过了左下角与右上角两个端点，还经过了中间的一些格点，手玩一下几个数据可以发现，经过的格点数是 $gcd(i, j) - 1$ 个。

所以，方案个数就是 $(i + 1) \times (j + 1) - 4 - (gcd(i, j) - 1)​$ 。

注意此处图形可以翻转，所以答案要乘二。

所以，对于每个子矩阵，完全覆盖的三角形个数就是
$$
4 \times (i - 1) \times (j - 1) + 2 \times [(i - 1) + (j - 1) + (i + 1) \times (j + 1) - 4 - (gcd(i, j) - 1)]
$$
化简后就是
$$
6 \times i \times j - 2 \times gcd(i, j)
$$

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#define lowbit(x) ( x & -x )
#define debug(x) (cout << "#x = " << x << endl)
#define re register
#define For(i, j, k) for(re int i = (j); i <= (k); i++)
#define foR(i, j, k) for(re int i = (j); i >= (k); i--)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll inf = 0x3f3f3f3f3f3f;

ll m, n, ans = 0; 

namespace IO {

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = (x << 3) + (x << 1) + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if ( x < 0 ) putchar ( '-' ), x = -x;
        if ( x > 9 ) write ( x / 10 );
        putchar ( x % 10 | 48 );
    }

    inline void wrn ( ll x ) { write (x); putchar ( ' ' ); }

    inline void wln ( ll x ) { write (x); putchar ( '\n' ); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

inline ll gcd ( ll a, ll b ) { return !b? a: gcd (b, a % b); }

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    m = read(), n = read();
    For ( i, 1, m ) For ( j, 1, n )
        ans += ( m - i + 1 ) * ( n - j + 1 ) * ( 6 * i * j - 2 * gcd (i, j) );
    return wln (ans), 0;
}

/*
2 2

76
*/

题目链接