3505: [Cqoi2014]数三角形
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 851 Solved: 525
[Submit][Status][Discuss]
Description
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
Sample Input
2 2
Sample Output
76
数据范围
1<=m,n<=1000
HINT
Source
【题解】
等下要刷一道su套su，先刷道水题压压gin。
首先在n*m个点中任取三个。
接着减去三点共线的：同行、同列、斜率不为0的。
对于斜线，枚举两点的坐标差，那么易求这样的点对的个数、两点之间的整点数。
那么就阔以辣！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
ll n,m,i,j;
ll gcd(int x,int y){
if (!(x%y))return y;else return gcd(y,x%y);
}
int main(){
scanf("%lld%lld",&n,&m);
n++;m++;
ll ans=(n*m-2)*(n*m-1)*n*m/6;
ans-=n*(m-2)*(m-1)*m/6;
ans-=m*(n-2)*(n-1)*n/6;
for (i=1;i<n;i++)
for (j=1;j<m;j++)
ans-=2*(n-i)*(m-j)*(gcd(i,j)-1);
printf("%lld\n",ans);
}
评论 (0)
