LUOGU P3166 数三角

作者: ffacs 分类: 题目 发布时间: 2019-12-31 09:16

https://www.luogu.org/problemnew/show/P3166

Problem Description

给定一个\(n*m\)的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。

Input

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

Output

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

Solution

先算一下任选三个点的个数。我们设函数$cal(x)=(x)*(x-1)*(x-2)/6$,也就是$C_{n}^{3}/3!$ $Cal((n+1)*(m+1))$ 然后减去图中三点共线的组合数,垂直坐标轴的很好算,分别是$Cal(n+1)*(m+1)$和$Cal(m+1)*(n+1)$。然后再求一下斜的的数目。其实每一个三点共线,我们都可以看成是两个端点是一个矩形的顶点,然后处于中间的那个点是对角线上横竖线的交点。比如如果两个端点分别是$(1,1)和(3,3)$那么这个矩形的对角线就穿过了$(2,2)$如果两个端点分别是$(1,1)和(5,9)$那么对角线是穿过$(2,3),(3,5),(4,7)$的。怎么算长宽分别为$n,m$的矩形对角线穿过的整点数呢?答案是$gcd(n,m)-1$,很显然我就不证明了。那么一个长宽分别为$x,y$的矩形里有多少个长宽为$n,m$的矩形呢$(n \leq x并且m\leq y)$? 答案是$(x-n+1)*(y-m+1)$,想象一下把小矩形放在大矩形里移动,往左右能移动$(x-n)$下,往上下能移动$(y-m)$下,每一次移动都得到的是一个位置不同大小相等的矩形。然后每个矩形是有两条对角线的。最后答案就出来了

int gcd(int a,int b){
    return  b==0?a:gcd(b,a%b);
}
ll cal(ll a){
    return  a*(a-1)*(a-2)/6;
}
int main(){
    int n,m;
    while (cin>>n>>m){
        ll ans=0;
        for(rg int i=1;i<=n;i++){
            for(rg int j=1;j<=m;j++){
                ans-=(n-i+1)*(m-j+1)*2*(gcd(i,j)-1);
            }
        }
        cout<<ans+cal((n+1)*(m+1))-cal(n+1)*(m+1)-cal(m+1)*(n+1)<<endl;
    }
    return  0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注