首页 > 代码库 > 【bzoj3505】 Cqoi2014—数三角形
【bzoj3505】 Cqoi2014—数三角形
http://www.lydsy.com/JudgeOnline/problem.php?id=3505 (题目链接)
题意
给定一个n*m的网格，请计算三点都在格点上的三角形共有多少个。
Solution
$${ans=平面中选三个点的方案数-三点共线的方案数}$$
$${ans=C_{(n+1)*(m+1)}^{3}-(n+1)*C_{m+1}^{3}-(m+1)*C_{n+1}^{3}-斜的三点共线的方案数}$$
斜的三点共线方案数不会求。。左转题解：http://blog.csdn.net/zhb1997/article/details/38474795
细节
LL
代码
// bzoj3505#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 10000000#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int n,m;LL c[2000010][4];int gcd(int a,int b) { return b==0 ? a : gcd(b,a%b);}int main() { scanf("%d%d",&n,&m); for (int i=0;i<=(n+1)*(m+1);i++) c[i][0]=1; for (int i=1;i<=(n+1)*(m+1);i++) for (int j=1;j<=min(3,i);j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; LL ans=c[(n+1)*(m+1)][3]-(n+1)*c[m+1][3]-(m+1)*c[n+1][3]; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { LL x=gcd(i,j)+1; if (x>2) ans-=(x-2)*2*(n-i+1)*(m-j+1); } printf("%lld",ans); return 0;}
【bzoj3505】 Cqoi2014—数三角形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。