BZOJ 3505 [Cqoi2014]数三角形

Description#

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

Input#

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

Output#

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

Sample Input#

2 2

Sample Output#

76

数据范围#

1<=m,n<=1000

题解#

先用组合数算出所有的可能

在 Gcd 去掉在一条线上的就可以了

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5
long long c[1000005][4];
6
long long gcd(long long a, long long b)
7
{
8
    return b == 0 ? a : gcd(b, a % b);
9
}
10
int main()
11
{
12
    long long n, m;
13
    scanf("%lld%lld", &n, &m);
14
    n++, m++;
15
    c[0][0] = 1;
16
    for (long long i = 1; i <= n * m; i++)
17
    {
18
        c[i][0] = 1;
19
        for (long long j = 1; j <= 3; j++)
20
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
21
    }
22
    long long ans = c[n * m][3];
23
    ans -= c[n][3] * m;
24
    ans -= c[m][3] * n;
25
    for (long long i = 1; i < n; i++)
26
    {
27
        for (long long j = 1; j < m; j++)
28
        {
29
            long long Gcd = gcd(i, j);
30
            if (Gcd > 1)
31
                ans -= 2 * (Gcd - 1) * (n - i) * (m - j);
32
        }
33
    }
34
    printf("%lld", ans);
35
}