题目描述
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。注意三角形的三点不能共线。
输入格式
输入一行，包含两个空格分隔的正整数m和n。
输出格式
输出一个正整数，为所求三角形数量。
输入输出样例
输入 #1
2 2输出 #1
76说明/提示
数据范围 1<=m,n<=1000
题解
首先，选三个点的方案是C((n+1)*(m+1),3)
然后减去三点共线的方案数即可
在一行共线的方案数为C(n+1,3)*(m+1)//m+1列
在一列共线的方案数为C(m+1,3)*(n+1)//n+1行
考虑在一条斜线上共线
假设左下方的点到右上方的点的向量为(i,j)
那么，他中间有gcd(i,j)-1个格点
而在(n+1)*(m+1)的图里可以放(n+1-i)*(m+1-j)个这样的向量
而它也有可能是从坐上到右下，方案数一模一样
所以要求的就是∑(i=1)(n)∑(j=1)(m)[ (n+1-i)*(m+1-j)*(gcd(i,j)-1)*2]
为什么我会如此zz地枚举斜线的斜率。。。枚举两个点找第三个点就好了。。。我整个人都傻了
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 long long n,m; 5 inline long long C(long long x) {if(x<3) return 0;return x*(x-1)*(x-2)/6;} 6 inline long long gcd(long long x,long long y) {if(y==0) return x; return gcd(y,x%y);} 7 int main() 8 { 9 scanf("%lld%lld",&n,&m); long long ans=C((n+1)*(m+1))-(m+1)*C(n+1)-(n+1)*C(m+1); 10 11 for(long long i=1;i<=n;i++) 12 for(long long j=1;j<=m;j++) 13 ans-=(n+1-i)*(m+1-j)*(gcd(i,j)-1)*2; 14 15 16 printf("%lld",ans); 17 return 0; 18 }