CQOI 2014 数三角形（乱搞）

发表于 |
字数统计: 395字 | 阅读时长 ≈ 2min

【CQOI2014】数三角形

问题描述

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

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

输入格式

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

输出格式

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

样例输入：

1 1

样例输出：

4

提示

对于30%的数据，1<=m,n<=10

对于100%的数据，1<=m,n<=1000

这题直接考虑用$C_{(n+1)(m+1)}^{3}$减去三点共线的方案数。

考虑统计三点共线的方案数，我们考虑枚举两个点位置关系，然后算出两点间的整点数。然后乘上这样的两个点的数目就行了。两点间整点数就是$gcd(x_2-x_1,y_2-y_1)-1$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll unsigned long long
using namespace std;
ll n,m,ans;
ll C(ll n,ll m)
{
	if(n<m)return 0;
	if(m==2)return n*(n-1)/2;
	if(m==3)return n*(n-1)/2*(n-2)/3;
}
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);}
int main()
{
	ll i,j,k,x,y;
	scanf("%lld%lld",&n,&m);
	ans=C((n+1)*(m+1),3);
	ans-=(n+1)*C(m+1,3)+(m+1)*C(n+1,3);
	for(i=1;i<=n+1;i++)
	for(j=1;j<=m+1;j++)
	{
		k=gcd(i,j);if(k==1)continue;
		ans-=(n+1-i)*(m+1-j)*(k-1)*2;
	}
	printf("%lld",ans);
}