首页/新闻资讯/正文详情

矩形对角线问题

发布时间:2026/11/20 5:10:56 来源:云帆数科 栏目:资讯中心
矩形对角线问题
将一个长为m宽为n的矩形划分成 m * n 个单元格作一条对角线标记该对角线与单元格的交点,有如下结论单条对角线经过的单元格数量为 m n - gcd(m,n)从 (0,0) 到 (m,n) 的直线在单位格中经过的格点包括端点数量是 gcd(m,n) 1如果只算内部格点就是 gcd(m,n) - 1单条对角线的交点数|S1| m n 1 - gcd(m,n) 两条对角线共同的交点数:2*(a b - gcd(a,b) - 1) - (a%20 || b%20 ? 1 : 0)。1.单条对角线经过的单元格数量为mn-gcd(m,n)1若m和n互为质数即gcd(m,n)1此时对角线与矩形只有两个端点在格点上内部没有位于格点的交点。ps:当横向交点与纵向交点重合时重复计算交点需减去。可知横向有m1个交点蓝色紫色纵向有n1个交点粉色紫色两个端点各被水平和竖直边界重复计算一次紫色所以要减去2共有(m1)(n1)-2mn个交点mn个交点将对角线分成mn-1段每段经过1个单元格共经过mn-1个单元格。2当m和n不互质时令d为二者的最大公约数即gcd(m,n)d, 此时m/d和n/d互质。取长m/d、宽n/d的小矩形此时由1可知对角线经过m/dn/d-1个单元格,大矩形共经过d*(m/dn/d-1)mn-gcd(m,n)个单元格。2.从 (0,0) 到 (m,n) 的直线经过的格点包括端点数量是 gcd(m,n) 1内部格点数是 gcd(m,n) - 1令gcd(m,n) dmn), 则m是n的d倍x 和 y n * x (0xd,x取整) 均为整数此时x,y)在格点上。因此包括端点的格点数为gcd(m,n) 1,内部格点数为gcd(m,n)-1。3.单条对角线的交点数|S1| m n 1 - gcd(m,n)|S1| 垂直线数 水平线数 - 顶点数。由2可知|S1| (m 1) (n 1) - (gcd(m,n) 1) m n 1 - gcd(m,n)。4.两条对角线共同的交点数:2*(a b - gcd(a,b) - 1) - (a%20 || b%20 ? 1 : 0)两条对角线唯一的交点是矩形墙壁的中心点。只有当这个中心点恰好落在某条网格线上时它才会被我们计入 |S1| 和 |S2|。墙壁的中心点坐标可以表示为 (m/2,n/2)。每条对角线内部交点数为 m n - gcd(m,n) - 1两条合计2*(m n - gcd(m,n) - 1)如果 m 和 n 有一个是偶数中心点就会落在网格线上并被重复计算所以要减 1。因此答案 2*(m n - gcd(m,n) - 1) - (m%20 || n%20 ? 1 : 0)。练习墙壁划线容斥原理

相关推荐

Agent Skills开发指南:Python与TypeScript生态实践
Agent Skills开发指南:Python与TypeScript生态实践

1. Agent Skills生态全景概览在当今开源生态系统中,Agent Skills正成为开发者工具箱中不可或缺的组成部分。这些技能仓库为开发者提供了即插即用的功能模块,大幅降低了构建智能代理系统的门槛。GitHub作为全球最大的代码托管平台,汇聚了最活跃… · 2026/11/18 19:08:29

Cursor错误日志无法关联Git blame?破解VS Code DevTools与Cursor Runtime日志时序对齐难题(含TS类型守卫自动注入脚本)
Cursor错误日志无法关联Git blame?破解VS Code DevTools与Cursor Runtime日志时序对齐难题(含TS类型守卫自动注入脚本)

更多请点击: https://codechina.net 第一章:Cursor错误日志系统的架构本质与设计契约 Cursor 错误日志系统并非传统意义上的中心化日志收集器,而是一个面向开发会话(dev-session)的上下文感知型诊断基础设施。其架构本… · 2026/11/17 11:23:54

API 中转服务怎么测:OpenAI SDK 兼容性、流式输出与错误排查
API 中转服务怎么测:OpenAI SDK 兼容性、流式输出与错误排查

很多开发者第一次选择 API 中转服务时,最先比较的是价格和模型数量。但真正接入项目后,影响使用体验的往往是另外几件事:OpenAI SDK 是否兼容、流式输出会不会中断、错误码是否清楚,以及出现故障后能不能快速定位。 本文不做“哪家… · 2026/11/17 20:18:02

常州特种工考试过期怎么办?真实经历告诉你怎么复审延期
常州特种工考试过期怎么办?真实经历告诉你怎么复审延期

常州特种工考试过期怎么办?真实经历告诉你怎么复审延期 证书过期了不知道怎么复审延期?我身边就有个老电工,去年证书刚好过期,结果因为没及时处理,被单位辞退了。这不是危言耸听,而是很多特种作业人员在现实中遇到的真实经历。常州特种工考试每年都有大… · 2026/11/20 5:10:05

和龙考电工证怎么考?实操考试心里没底怕挂科?官方报名入口在这
和龙考电工证怎么考?实操考试心里没底怕挂科?官方报名入口在这

和龙考电工证怎么考?实操考试心里没底怕挂科?官方报名入口在这 实操考试心里没底怕挂科?别急,今天就带你从零了解【和龙考电工证】怎么考、考什么、考不过怎么办,还有你关心的 官方报名入口 到底在哪。… · 2026/11/20 5:10:05

宁夏低压电工作业实操怎么考不被坑?电子证书报名全攻略
宁夏低压电工作业实操怎么考不被坑?电子证书报名全攻略

宁夏低压电工作业实操怎么考不被坑?电子证书报名全攻略 你是不是也遇到过这种情况:想考低压电工证,网上一搜全是“包过”“包拿证”的广告,但你心里没底,怕被坑?尤其是宁夏地区的朋友们,面对五花八门的培训机构和中介,真的不知道该相信谁。别急,今天… · 2026/11/20 5:10:05

电工证到期多久算逾期 上岗必备怎么安排复审才不耽误工作
电工证到期多久算逾期 上岗必备怎么安排复审才不耽误工作

电工证到期多久算逾期 上岗必备怎么安排复审才不耽误工作 实操考试心里没底怕挂科,尤其是咱们一线电工,证书到期了又怕错过复审时间,影响正常上岗,这种焦虑很多人都有。其实,只要提前规划好,电工证到期多久算逾期并不是难题,关键在于了解清楚复审规则… · 2026/11/20 5:10:05

罗萍考电工证过期了不知道怎么复审多少钱
罗萍考电工证过期了不知道怎么复审多少钱

罗萍考电工证过期了不知道怎么复审多少钱 证书过期了不知道怎么复审延期,这事儿可真让人头疼。罗萍最近就遇到了这个问题,她手里那本低压电工证已经快到期了,但一想到复审流程,她就犯愁: 多少钱… · 2026/11/20 5:10:05

2026河南最新政策下电工作业考试城市报考攻略与避坑指南
2026河南最新政策下电工作业考试城市报考攻略与避坑指南

2026河南最新政策下电工作业考试城市报考攻略与避坑指南 怕考不过白交培训费?2026年河南电工作业考试城市报考政策变化大,你得先搞懂这些事。不管是低压电工还是高压电工,今年的政策和考试安排,直接影响你能不能顺利拿证。别再稀里糊涂花钱了,这… · 2026/11/20 5:09:05

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/19 16:06:02

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/19 17:40:37

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/19 17:50:07

建设厅特种工周三报名怎么弄?上岗必备别被中介坑
建设厅特种工周三报名怎么弄?上岗必备别被中介坑

建设厅特种工周三报名怎么弄?上岗必备别被中介坑 不知道去哪报名怕被中介坑?作为商丘某高校工程类应届毕业生,小李最近就遇到了这样的困扰。他刚毕业,正在找实习岗位,发现很多工地都要求持有特种作业操作证,尤其是【建设厅特种工周三报名】这个时间点,… · 2026/11/20 0:00:54

中专考的中级电工证内部消息全攻略
中专考的中级电工证内部消息全攻略

中专考的中级电工证内部消息全攻略 你中专毕业,手头有中级电工证,但不知道从哪开始报名,怕被中介坑?别急,这篇文章就是为你量身定制的“内部消息”,帮你避开报名陷阱,稳稳拿到证书。… · 2026/11/20 0:00:54

外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价
外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价

外省电工证能转过来吗?电子证书怎么查电工作业教学效果评价 之前考的证在外省能不能转过来?这几乎是所有在外地打拼的电工从业者最关心的问题。特别是像洛阳这样的工业城市,很多电工证是在外地考的,现在想在当地用,流程是不是很复杂?其实,只要搞清楚… · 2026/11/20 0:00:54

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:25

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:32

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码