数三角形

· · 个人记录

题目描述

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

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

输入

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

输出

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

样例输入

2 2

样例输出

76

提示

1<=m,n<=1000

题解

先算出任意取三个点的方案数，减去三个同在每一行和同在某一列的方案数，还有

一种就是同在一条斜直线上的情况公式是(m-i)(n-j)(gcd(i,j)-1)。gcd(i,j)+1可以算出

横着长度为i，竖着长度为j的直角三角形斜边上的整点个数，再减去端点的2个点就

是(gcd(i,j)-1)，(m-i)*(n-j) 是在找可以放多少个这样的三角形。


#include<bits/stdc++.h>
using namespace std;
long long n,m,ans=0;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    scanf("%lld %lld",&n,&m);
    n++;m++;
    ans=(n*m)*(n*m-1)*(n*m-2)/6;
    ans-=n*(n-1)*(n-2)/6*m;
    ans-=m*(m-1)*(m-2)/6*n;
    for(int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            ans-=(m-i)*(n-j)*(gcd(i,j)-1)*2;
        }
    }
    printf("%lld",ans);
    return 0;
}