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;
}

  

最新文章

  1. 用Powershell启用Windows Azure上的远程桌面服务
  2. 【转】C# 的Brush 及相关颜色的操作
  3. 【集合框架】JDK1.8源码分析之Collections &amp;&amp; Arrays(十)
  4. 设置树莓派3 B+的静态IP
  5. JSON的简单例子
  6. 修改myeclipse的servlet模板
  7. 全面解析SQL SERVER 的左右内连接
  8. Hyper-V避免使用快照
  9. mysql分表分库
  10. OpenCascade简介
  11. NFA的实现
  12. Ajax实现带进度条的文件上传
  13. word20161226
  14. git pull和本地文件冲突
  15. javaScript系列 [02]-javaScript对象探析
  16. Echarts-图表根据值的不同展示成不同的颜色
  17. C#调试心经
  18. Lombok 继承时应注意的点
  19. 如何自定义微信小程序swiper轮播图面板指示点的样式
  20. 使用 IntraWeb (4) - 页面布局之 TIWRegion

热门文章

  1. Python语言Web开发框架web2py
  2. php关键词替换的类(避免重复替换,保留与还原原始链接)
  3. python-切片 迭代 生成器
  4. webForm(三)——三级联动
  5. FLUSH TABLE WITH READ LOCK详解
  6. 笔记整理之 Bulk Insert
  7. Oracle创建表空间和用户
  8. Asp.Net MVC+BootStrap+EF6.0实现简单的用户角色权限管理5
  9. 4412开发板搭建Uboot、Kernel和Android4.0的编译环境方法
  10. 理解Docker(1):Docker 安装和基础用法