Description

Input

输入一行，包含两个空格分隔的正整数m和n。

Output

输出一个正整数，为所求三角形数量。

Sample Input

输入1： 1 1 输入2： 2 2

Sample Output

输出1： 4 输出2： 76

Data Constraint

对于30%的数据 1<=m,n<=10 对于100%的数据 1<=m,n<=1000

---

解题报告

一个显然的结论是：在这个网格图里，选三个点的方案数是C(3,(n+1)*(m+1))。 然后我们就逆向思维一下，得出：总方案数=选三个点的方案数-三点共线的方案数。 现在我们就是要求一个三点共线的方案数了。 方法：首先我们枚举这个三点共线的“三角形”的最长边（长度可能相同，但是方向不同），对于每一个最长边我们可以看成一个向量（x,y）。在这个向量上穿过的点数为gcd(x,y)+1。则这个向量能形成的三点共线的“三角形”数就等于gcd(x,y)-1。而这种向量在网格图上不同的个数就等于(n-x+1)*(m-y+1)。就这样，我们就能求出不同三角形的个数了。

---

Source Code

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,m; long long ans; long long s[1000*1000+10]; long long c(int x,int y) { long long s=1; for (int i=x-y+1;i<=x;++i) s*=i; for (int i=2;i<=y;++i) s/=i; return s; } int gcd(int x,int y) { if (y==0) return x; else return gcd(y,x%y); } void init() { scanf("%d%d",&n,&m); n++; m++; } int main() { init(); ans=c(n*m,3); ans-=m*c(n,3); ans-=n*c(m,3); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) ans-=(n-i)*(m-j)*(gcd(i,j)-1)*2; printf("%lld\n",ans); return 0; }