BZOJ 3505 [Cqoi2014]数三角形

Description

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

Input

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

Output

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

Sample Input

2 2

Sample Output

76

数据范围

1<=m,n<=1000

题解

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

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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long c[1000005][4];
long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    long long n, m;
    scanf("%lld%lld", &n, &m);
    n++, m++;
    c[0][0] = 1;
    for (long long i = 1; i <= n * m; i++)
    {
        c[i][0] = 1;
        for (long long j = 1; j <= 3; j++)
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    long long ans = c[n * m][3];
    ans -= c[n][3] * m;
    ans -= c[m][3] * n;
    for (long long i = 1; i < n; i++)
    {
        for (long long j = 1; j < m; j++)
        {
            long long Gcd = gcd(i, j);
            if (Gcd > 1)
                ans -= 2 * (Gcd - 1) * (n - i) * (m - j);
        }
    }
    printf("%lld", ans);
}