BZOJ 3505 【Cqoi2014】 数三角形

时间:2023-05-06 11:00:26

Description

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

下图为4x4的网格上的一个三角形。

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

Input

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

Output

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

HINT

数据范围
$1\leqslant m,n \leqslant 1000$

  这道题一眼看去有一个非常显然的想法,那就是先用组合数算出任选三点出来的方案数,最后再减去三点共线的情况即可。那么关键就在于如何求三点共线的数目。

  首先,我们要用到一个公式:设两个整点分别为$(x_1,y_1)$,$(x_2,y_2)$,那么两点之间连线上的整点数目为$gcd(|x_2-x_1|,|y_2-y_1|)$。

  我觉得这个公式需要证明一下(其实很简单)。

  首先,这条直线可以平移一下,使得$x_1=y_1=0$。为了考虑方便,我们这里还设$x_2 \geqslant 0,y_2 \geqslant 0$

  设$\Delta x=x_2,\Delta y =y_2$(只是为了好看一点),连线上整点的坐标为$(x,y)$,那么显然有:$$\frac{x}{\Delta x}=\frac{y}{\Delta y}$$

  设$r=gcd(\Delta x,\Delta y)$,$\Delta x=ar$,$\Delta y=br$,那么有:$$xb=ya$$

  由于$a,b$互质,$x,y$为整数,于是我们就得到了$$x=ka,y=kb(k \in Z)$$;

  由于$0 \leqslant x \leqslant \Delta x,0\leqslant y \leqslant \Delta y$且$x,y$为整数

  所以$x,y$的取值共有$\Delta x / a=\Delta y/b=gcd(\Delta x,\Delta y)$种

  除去$x=\Delta x,y=\Delta y$这组解,这两点连线上共有$gcd(\Delta x,\Delta y)-1$个整点。

  接下来我们可以直接枚举线段,然后计算有线段上有多少个整点;然而这样复杂度是$O(n^2m^2)$的。

  然后,显然每一条线段经过平移,使它的左端点在矩形左下角或者左上角。由于向下和向上的线段对称,所以只需要计算一种即可。

  所以就固定一个端点为$(0,0)$,枚举另外一个端点在哪里,计算一下即可。

  下面贴代码(话说这么一道题我好像讲复杂了):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std;
typedef long long llg; int n,m;
llg ans,x; int gcd(int a,int b){
if(!b) return a;
int r=a%b;
while(r) a=b,b=r,r=a%b;
return b;
} int main(){
File("a");
scanf("%d %d",&n,&m);
x=(n+1)*(m+1); ans=x*(x-1)*(x-2)/6;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(i|j){
llg x=(llg)(n-i+1)*(llg)(m-j+1);
ans-=x*(llg)(gcd(i,j)-1);
if(i && j) ans-=x*(llg)(gcd(i,j)-1);
}
printf("%lld",ans);
return 0;
}