NC50594. 数三角形
描述
给定一个
的网格，请计算三点都在格点上的三角形共有多少个。下图为
的网格上的一个三角形。
输入描述
输入一行，包含两个空格分隔的正整数m和n。
输出描述
输出一个正整数，为所求三角形数量。
示例1
输入:
2 2
输出:
76
NC50594. 数三角形
描述
输入描述
输入一行，包含两个空格分隔的正整数m和n。
输出描述
输出一个正整数，为所求三角形数量。
示例1
输入:
2 2
输出:
76
C++11(clang++ 3.9) 解法, 执行用时: 56ms, 内存消耗: 392K, 提交时间: 2020-02-05 19:46:12
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c(ll x)
{
return x*(x-1)*(x-2)/6;
}
int n,m;
ll ans;
int main()
{
scanf("%d%d",&n,&m);
++n;
++m;
ans=c(n*m)-c(n)*m-c(m)*n;
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
ans-=(__gcd(i,j)-1)*(n-i)*(m-j)*2;
printf( "%lld\n",ans);
return 0;
}