bzoj3505 / P3166 [CQOI2014]数三角形
2024-10-10 01:58:34
前置知识:某两个点$(x_{1},,y_{1}),(x_{2},y_{2})\quad (x_{1}<x_{2},y_{1}<y_{2})$所连成的线段穿过整点的个数为$gcd(x_{2}-x_{1},y_{2}-y_{1})-1$
“注意三角形的三点不能共线。”
暗示你可以处理出总方案再减去三点共线的方案。
显然,总方案就是在$(n+1)*(m+1)$个点中任选$3$个。于是$tot=C((n+1)*(m+1),3)$
现在我们要算出三点共线的方案
对于直线上的三点共线,显然$tot1=n*C(m,3)+m*C(n,3)$
对于斜线上的三点共线,我们可以根据前置知识↑↑枚举。
然鹅暴力枚举复杂度是达到$O(n^{2}m^{2})$的
所以我们需要转化
注意到其实我们可以只枚举$l=x_{2}-x_{1},r=y_{2}-y_{1}$,相当于把这两个数据看做一个矩形的长和宽。
蓝后我们要算出整个大矩形中有几个这样的小矩形:$(n-l+1)*(m-r+1)$
每个矩形中包含$2$条对角线,所以$tot2*=2$
所以斜线上的三点共线$tot2=\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)-1)*(n-i+1)*(m-j+1)$
代码中为了方便事先把$n,m$都$+1$
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
ll m,n,ans;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
scanf("%lld%lld",&n,&m);++n;++m;
ll tmp=n*m;
ans=tmp*(tmp-)*(tmp-)/;
ans-=n*m*(m-)*(m-)/;
ans-=m*n*(n-)*(n-)/;//减去横向和纵向的三点共线
for(int i=;i<n;++i)
for(int j=;j<m;++j)
ans-=1ll*(gcd(i,j)-)*(n-i)*(m-j)*;
printf("%lld",ans);
return ;
return ;
}
最新文章
- 对于C(n,k)取模
- 使用MongoDB作为后台数据库的尝试
- V​S​2​0​1​2​快​捷​键
- viewpage的使用
- C++中求两个正整数的最大公约数和最小公倍数
- LLDB调试基本使用
- mac下的改装人生——关于ssd
- 服务器端打开office然后采用虚拟打印 转换成pdf
- python日期时间处理
- php 登陆动作详解
- 短信发送接口被恶意访问的网络攻击事件(四)完结篇--搭建WAF清理战场
- Linux入门(17)——Ubuntu16.04显示内存CPU网速等(System Monitor)
- Java开源生鲜电商平台-性能优化以及服务器优化的设计与架构(源码可下载)
- 放下技术,是PM迈出的第一步
- .class和.getClass()的区别
- 20175202 《Java程序设计》第五周学习总结
- hadoop3.x.x错误解决
- China Operating System 电脑操作系统 2016全球互联网排名
- day_11 py 名片管理系统
- Python Mock的入门(转)
热门文章
- Docker添加镜像加速器
- POJ-1644 To Bet or Not To Bet(概率DP)
- HDU 1083 - Courses - [匈牙利算法模板题]
- MySQL在windows下的图形安装
- web移动端开发经验总结
- web前端开发笔记(2)
- Ubuntu 14.04 使用速度极快的Genymotion 取代蜗牛速度的原生AVD模拟器
- nginx ipv4 ipv6 chrome /firefox remote-address/chrome://net-internals/dns
- linux rz sz的安装
- Android内存泄漏的本质原因、解决办法、操作实例