Bzoj3505 [cqoi2014]数三角形

Posted by yjjr's blog on February 6, 2018

标签:排列组合,数学

Description

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

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

Input

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

Output


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

Sample Input

2 2

Sample Output

76

数据范围

1<=m,n<=1000

我们可以利用补集的思想,用排列组合C(n*m,3)算出总方案数,之后减去一些不符合条件的方案

1.     三点共一条水平直线

2.     三点共一条竖直直线

3.     三点共一条斜线(用gcd判断和计算)

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
const int maxn=1e6+6;
LL c[maxn][4],n,m,ans,t;

int main()
{
	n=read(),m=read();
	n++,m++;
	c[0][0]=1;
	rep(i,1,n*m){
		c[i][0]=1;
		rep(j,1,3)c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	ans=c[n*m][3];
	ans-=n*c[m][3];
	ans-=m*c[n][3];
	rep(i,1,n-1)
	    rep(j,1,m-1){
			t=gcd(i,j)+1;
			if(t>2)ans-=(t-2)*2*(n-i)*(m-j);
		}
	printf("%lld\n",ans);
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr