题目描述
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。
输入输出格式
输入格式：
输入一行，包含两个空格分隔的正整数m和n。
输出格式：
输出一个正整数，为所求三角形数量。
输入输出样例
说明
数据范围
bzoj上是1<=m,n<=1000
以为有啥推的关系，后来发现不好推，就开始想怎么算。
总方案数 C ( (n+1)*(m+1) ,3 );
在减去三点一线的 水平，竖直的，斜着的
前两个好算
对于斜着的
枚举对角线(左下-右上), 即(0, 0)-(x, y), 我们发现这种情况有(n-y)*(m-x)*2(算上左上-右下的)种, 然后中间有gcd(x, y)-1个点(不合法), 乘起来就好了 我们枚举一下边上两个点的横纵坐标之差(i,j)。 那么中间的点可选的位置就是gcd(i,j)-1;然后再乘上这种直线的条数即可
1 #include "bits/stdc++.h"
2 #define inf 1000000000;
3 using namespace std;
4 typedef long long ll;
5
6 int n,m;
7
8 ll C(ll a, ll b)
9 {
10 if(b>a) return 0;
11 else if(b==a)return 1;
12 else return a*(a-1)*(a-2)/6;
13 }
14
15 int main()
16 {
17 cin>>n>>m; ll tot=(n+1)*(m+1);
18 ll ans=tot*(tot-1)*(tot-2);
19 ans/=6;
20 ll t1=n/2,t2=m/2;
21 //cout<<ans<<endl;
22 ans-=C(n+1,3)*(m+1);
23 ans-=C(m+1,3)*(n+1);
24 // if(n+1>=3)ans-=(n+1-3+1)*(m+1);
25 // if(m+1>=3) ans-=(m+1-3+1)*(n+1);
26 for (int i=1;i<=n;i++)
27 for (int j=1;j<=m;j++)
28 {
29 ans-=(n-i+1)*(m-j+1)*(__gcd(i,j)-1)*2;
30 }
31
32 cout<<ans;
33
34
35
36 }