BZOJ 3505
3505: [Cqoi2014]数三角形
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1171 Solved: 703
[Submit][Status][Discuss]
codevs3693 数三角形同题:http://codevs.cn/problem/3693/
Description
给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
Input
输入一行,包含两个空格分隔的正整数m和n。
Output
输出一个正整数,为所求三角形数量。
Sample Input
Sample Output
数据范围
1<=m,n<=1000
HINT
Source
题解:
1、先不考虑三角形,从n*m的网格里面任意选取3个点,一共有多少种方案? C(n*m,3) 现在,这3个点必须要构成三角形,有哪种情况需要去除? 三点共线的情况。 我们用C(n*m,3)减去三点共线的情况,最后得到的就是答案。
2、一个n*m的网格,有多少种选法,选择3个点是三点共线的? 这是一个5*7的网格
如果固定左上角和右下角这两个点,一共有多少个点和它们共线?
3、
大三角形和小三角形是相似的 小三角形的直角边长x’和y’应该是大三角形的直角边长X和Y的约数 所能放下的点的个数-1是X/x’=Y/y’,这个数也是X的约数,同时也是Y的约数 所以最多能放gcd(X,Y)-1个点。
4、
回到刚才那个问题的话,一个n*m的网格,它的两条边的长度分别是n-1和m-1,所以对角线上最多有gcd(n-1,m-1)-1个点在格线上。 再看这道题本身,我们求有多少种选取三个点的选法,满足三点共线,可以分这两种情况 所在直线水平/竖直 所在直线是斜的
所在直线水平/竖直: n*C(m,3)+m*C(n,3) 所在直线是斜的: 先用一个双重循环,枚举三个点中以两头的两个点为对角线所构成的网格的大小 如果以这两个点为对角线构成了一个n’*m’的网格,则以它们为两头的点,一共有gcd(n’-1,m’-1)-1种选法可以三点共线
5、
AC代码:
#include<iostream>
#include<cstdio>
using namespace std;
#define ll unsigned long long
ll n,m;
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
ll C(ll x){
return x*(x-)/*(x-)/;
}
int main(){
cin>>n>>m;
ll ans=C((m+)*(n+));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(i||j) ans-=(gcd(i,j)-)*(n-i+)*(m-j+)*(i&&j?:);
}
}
cout<<ans<<endl;
return ;
}
最新文章
- Web API接口设计经验总结
- 【BZOJ 4636】蒟蒻的数列
- android 开发小记
- SCU3185 Black and white(二分图最大点权独立集)
- Cheatsheet: 2013 11.12 ~ 11.30
- php大力力 [002节]mac php环境安装,mamp安装 ,phpMyAdmin启动
- 在virtualbox上安装mac os mavericks遇到Missing Bluetooth Controller Transport问题解决办法
- 关于jsp中超链接的相对路径
- NET Core 构成体系
- 【iOS开发-48】九宫格布局案例:自己主动布局、字典转模型运用、id和instancetype差别、xib反复视图运用及与nib关系
- CSS3 转换2D transform
- tensorflow rnn 最简单实现代码
- [转]NSIS 制作安装包无法创建桌面快捷方式或无法删除开始菜单项
- leetcode — maximum-subarray
- 2014/08/31 Zushi
- Spark启动时的master参数以及Spark的部署方式
- 在window 2008r2开发服务器上安装MSMQ消息队列
- Logging模块 + traceback模块 + importlib模块 + requests模块
- google guice @inject comments
- 常见排序的JAVA实现和性能测试
热门文章
- UVA 11300 Spreading the Wealth
- Random的nextInt用法
- 使用ASP.NET 构建 Web 应用程序快速入门-8小时的免费培训视频
- c#与java webservice调用问题
- VS2012开发ActiveX插件 尝试1
- CreateProcess的使用方法
- Nginx目录保护、防盗链、限速及多域名处理
- iOS开发——UI篇OC篇&;layoutSubviews和drawRect
- C++中new与delete问题学习
- Computer Science Theory for the Information Age-1: 高维空间中的球体