首先算出任取三个点的情况，去掉三点共线。 三点共线有三种情况：竖着，横着，斜着。 斜着的点数就是程序里的num。为什么是gcd+1呢？考虑i/j的最简形式是p/q，(p*k,q*k)当k取遍0~gcd时，这gcd+1组坐标一定为整点。 还有就是算斜着的时候只要先算出(0,0)为起点的情况，之后平移即可。 PS本题预处理gcd会更快哦！
#include<cmath> #include<cstdio> #include<vector> #include <queue> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 1005 #define fo(i,a,b) for(i=a;i<=b;i++) #define fd(i,a,b) for(i=a;i>=b;i--) using namespace std; ll c[N*N][4]; int n,m,i,j,num; ll res; void pre_c() { int i,j; c[0][0] = 1; fo(i,1,n*m) { c[i][0] = 1; fo(j,1,3) c[i][j] = c[i-1][j-1]+c[i-1][j]; } } int getgcd(int a,int b) {return b==0?a:getgcd(b,a%b);} int main() { scanf("%d%d",&n,&m); n++; m++; pre_c(); res = c[n*m][3]; res -= n * c[m][3]; res -= m * c[n][3]; fo(i,1,n-1) fo(j,1,m-1) { num = getgcd(i,j) + 1; if (num <= 2) continue; res -= (num-2)*2*(n-i)*(m-j); } printf("%lld",res); return 0; }