3505: [Cqoi2014]数三角形
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 478 Solved: 293
[Submit][Status]
Description
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
Sample Input
2 2
Sample Output
76
数据范围
1<=m,n<=1000
HINT
Source
这道题我居然白痴得卡在了求三点共线组数上，最开始我的想法是枚举每一个斜率的直线，计算他们的条数与交点，但是至今我还是不知道怎么弄，正确的方法应该是枚举三点共线两端点的坐标差，然后可轻而易举求出这样的端点对数，中间点的位置数，即可解此题。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 10000
typedef long long qword;
int gcd(int x,int y)
{
return (x%y==)?y:gcd(y,x%y);
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int i,j,k,x,y,z;
int n,m;
scanf("%d%d",&n,&m);
n++;m++;
int tot=;
qword ans0,ans1=;
ans0=(qword)(m*n-)*(m*n-)*m*n/;
for (i=;i<n;i++)
{
for (j=;j<m;j++)
{
ans1+=(qword)(gcd(i,j)-)*(n-i)*(m-j);
}
}
ans1*=;
ans1+=(qword)(n-)*(n-)*n/*m;
ans1+=(qword)(m-)*(m-)*m/*n;
printf("%lld\n",ans0-ans1);
}