bzoj 3505 [Cqoi2014]数三角形
Description
给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4×4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行,包含两个空格分隔的正整数m和n。
Output
输出一个正整数,为所求三角形数量。
Sample Input
2 2
Sample Output
76
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),即通过平移找到多少条这样的线段。总数减去这些不合法线段个数就是答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#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); } |