「BZOJ3505」[CQOI2014] 数三角形
Description
给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4×4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行，包含两个空格分隔的正整数m和n。
Output
输出一个正整数，为所求三角形数量。
Sample Input
2 2
Sample Output
76
数据范围
1<=m,n<=1000
题解
首先在n*m个点选择任意3个
然后减去三点共线的
三点共线分三种情况，同一行，同一列，斜的用gcd算
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);} int n,m; ll c[1005005][4]; ll ans,tmp; void getc() { c[0][0]=1; for(int i=1;i<=n*m;i++) { c[i][0]=1; for(int j=1;j<=3;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; } } void solve() { ans=c[n*m][3]; ans-=n*c[m][3]; ans-=m*c[n][3]; for(int i=1;i<n;i++) for(int j=1;j<m;j++) { tmp=gcd(i,j)+1; if(tmp>2) ans-=(tmp-2)*2*(n-i)*(m-j); } } int main() { n=read();m=read(); n++;m++; getc(); solve(); printf("%lld",ans); return 0; } |
Subscribe
计数器 9863789
OI 课件=>
OI 课件=>