若若的三角形

Posted on by mannuan One min read
Table of Contents

时间限制：

C/C++语言 1000MS；其他语言 3000MS

内存限制：

C/C++语言 131072KB；其他语言 655360KB

题目描述：

若若有一个格子数为n*m的网格，现在若若想知道3个点都在格点上能形成的三角形有多少个（三点不能共线）

输入

一行两个数n和m
n,m<=1800

输出

三角形个数

样例输入

2 2

样例输出

76

# include<stdio.h>
# include<iostream>
# include<string.h>
# include<algorithm>
using namespace std;
int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b, a%b);
}
long long Com(int n, int r){
    if(n<r) return 0;
    if(n-r<r) r = n-r;
    int i,j;
    long long ret = 1;
    for(i=0,j=1;i<r;i++){
        ret*=(n-i);
        for(;j<=r&&ret%j==0;j++){
            ret /= j;
        }
    }
    return ret;
}
int main(){
    int n,m;
    while(scanf("%d%d", &n, &m)!=EOF){
        long long ans = Com((n+1)*(m+1),3);
        for(int i=2;i<=n;i++){
            for(int j=2;j<=m;j++)
            ans -= (long long)(gcd(i,j)-1)*(n-i+1)*(m-j+1)*2;
        }
        ans-=Com(n+1, 3)*(m+1);
        ans-=Com(m+1,3)*(n+1);
        printf("%lld\n", ans);
    }
    return 0;
}