大家好，又见面了，我是你们的朋友全栈君。
Description：
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4×4的网格上的一个三角形。
注意三角形的三点不能共线。
Hint：
1<=m,n<=1000
Solution：
直接算三角形肯定算死。
所以，先考虑所有的可能三角形。再减去不合法的三点共线的情况。
所有三角形：C((n+1)*(m+1),3)
不合法的情况怎么处理？？
开始的想法：
1.找所有的两端在坐标轴上的直线，算出来整点数:gcd(x,y)+1；再算上下，左右的直线。
但是发现可能有的不合法直线不过边框的整点！！bug
2.考虑直线的方程：ax+by+c=0
a，b，c是常整数。并且都在1~n（m）的范围内。
相当于求x，y的非负整数解的个数。（exgcd）
但是待定系数n^4，枚举系数n^3都不行。bug
正解：
优化一下
发现找直线非常复杂。
如果我们找线段呢？并且保证线段的两端都在整点上？相当于把直线根据整点拆开了
(a,b)(c,d）的线段中间的整点有gcd(abs(c-a),abs(d-b))-1个方案。
枚举线段减去中间放点的方案，这样还是n^4
发现，许多的线段本质上是一致的，只是平移了。
所以，我们只需要枚举所有的(0,0)(x,y),就可以了、。
平移的方案就是（n+1-x）*(m+1-y)相当于画出了一个矩形。
对于不是在坐标轴上的点，我们还要乘2，相当于上下一个对称情况。
Code：
#include<cstdio> #define LL long long int gcd[1010][1010]; int n,m; LL t,ans; inline int getgcd(int a,int b) { if (gcd[a][b])return gcd[a][b]; if (!a)return gcd[a][b]=b; if (!b)return gcd[a][b]=a; return gcd[a][b]=getgcd(b,a%b); } inline void calc() { for(int i=1;i<=m;i++)gcd[0][i]=i; for(int i=1;i<=n;i++)gcd[i][0]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) getgcd(i,j); } int main() { scanf("%d%d",&n,&m); calc(); t=(n+1)*(m+1); ans=t*(t-1)*(t-2)/6; for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) if (i||j) { if (!i||!j)ans-=(LL)(gcd[i][j]-1)*(n-i+1)*(m-j+1); else ans-=(LL)2*(gcd[i][j]-1)*(n-i+1)*(m-j+1); } printf("%lld",ans); }
转载于:https://www.cnblogs.com/Miracevin/p/9400674.html
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/107389.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
