bzoj 3505 [Cqoi2014]数三角形

Contents

Description
Input
Output
- Sample Input
- Sample Output
HINT
题解

Description

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

注意三角形的三点不能共线。

Input

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

Output

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

Sample Input

2 2

Sample Output

HINT

数据范围

1<=m,n<=1000

题解

随便选三个点C(N+1)(M+1),3，然后减去那些构成一条直线的。

有个定理(i,j)到(0,0)的连线上的整数点的个数是gcd(i,j)（包含(0,0)而不包含(i,j)）。

我们在坐标系内作线段，首先斜率为负数的通过翻转肯定能变成斜率为正数的，所以只需统计斜率为正数的（斜率为0或不存在的可以单独算）。

一条斜率>0的线段肯定能够通过平移使得左下端点和(0,0)重合，因此我们就到结论上来了，只需统计每个点和(0,0)连线上有多少点，然后乘上(N+1-i)*(M+1-j)，即通过平移找到多少条这样的线段。总数减去这些不合法线段个数就是答案。

#include <cstdio>
#include <cmath>
using namespace std;
long long n, m, num, ans;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
main() {
scanf("%lld%lld", &n, &m);
num = (n + 1ll) * (m + 1ll);
ans = num * (num - 1ll) * (num - 2ll) / 6ll;
for (long long i = 0; i <= n; ++i)
for (long long j = 0; j <= m; ++j) {
if (i == 0 && j == 0) continue;
num = (gcd(i, j) - 1ll) * (n - i + 1ll) * (m - j + 1ll);
if (i == 0 || j == 0) ans -= num;
else ans -= num << 1;
}
printf("%lld\n", ans);
}