3505: [Cqoi2014]数三角形
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 482 Solved: 295
[Submit][Status]
Description
给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行,包含两个空格分隔的正整数m和n。
Output
输出一个正整数,为所求三角形数量。
Sample Input
2 2
Sample Output
76
数据范围
1<=m,n<=1000
数据范围
1<=m,n<=1000
感谢ZKY,不然还要继续纠结
http://blog.csdn.net/iamzky/article/details/38733405
C(nm,3)-共线
直线共线 C(n,3)*m+C(m,3)*n
枚举斜着的矩阵, 矩阵上有gcd(i,j)-1个点,有(n-i)*(m-j)个矩阵,反方向*2
完了
注意重复的处理
#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive ************************************************/ ///////////////////////////////////////////////// #define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) ///////////////////////////////////////////////// LL n,m; ///////////////////////////////////////////////// LL gcd(LL a,LL b){return b?gcd(b,a%b):a; } ///////////////////////////////////////////////// void input() { scanf("%lld%lld",&n,&m);n++;m++; } void solve() { ///////////////////init/////////////////// LL ans=0,t; ////////////////calculate//////////////// t=n*m; ans = t * (t-1) * (t-2) / 6; ans -= n * m * (m-1) * (m-2) / 6; ans -= m * n * (n-1) * (n-2) / 6; rep(i,1,n) rep(j,1,m) //枚举斜率 { t=gcd(i,j)+1; if(t>=3) ans-=(t-2) * 2 *(n-i) * (m-j); } /////////////////output///////////////// printf("%lld\n",ans); } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(); solve(); #ifdef _TEST for(;;); #endif return 0; }