[bzoj3505 Cqoi2014] 数三角形 (容斥+数学)

传送门

Description

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

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

Input

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

Output

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

Sample Input

2 2

Sample Output

HINT

1<=m,n<=1000

Solution

首先思路肯定是随意三个点方案-三点共线方案

随意三个点方案随意求

主要求三点共线：

有个神奇的结论：节点坐标gcd-1 是矩形内的点个数也就是这个矩形确定两端点的方案数

只要枚举一个矩形大小然后平移什么的就行了

PS：注意特殊情况

Code

//By Menteur_Hxy

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}

int main() {

	LL n,m,t,ans;

	scanf("%lld %lld",&n,&m);

	t=(n+1)*(m+1);

	ans=t*(t-1)*(t-2)/6;

	for(int i=0;i<=n;i++)

		for(int j=0;j<=m;j++) {

			t=(gcd(i,j)-1);

			if(t<=0) continue;

			t*=(n-i+1)*(m-j+1);

			if(i&&j) ans-=t<<1;

			else ans-=t;//"特殊情况"

		}

	printf("%lld",ans);

	return 0;

}

巴特西