1310. 数三角形

题目链接:https://www.acwing.com/problem/content/1312/

首先不考虑三点共线的情况一共有 C_{nm}^{3} 种,现在来计算三点共线的情况

1.三点在一条直线上 n*C_{m}^{3}

2.三点在一条竖线上 m*C_{n}^{3}

3.三点在一条斜线上,正反斜线对称,仅需考虑一边的情况

 

 如果边上两点A,B确定那么有多少种共线情况呢,如图所示一共gcd(a,b)-1种情况。

然后对于每组a,b一共有(n-a-1)*(m-b-1)种位置,枚举a,b即可

Code

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}LL C(int n)
{return (LL)n * (n - 1) * (n - 2) / 6;
}int main()
{int n, m;cin >> n >> m;n ++, m ++ ;LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);cout << res << endl;return 0;
}

 计算网格内所有三点共线线段的数量

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/76832.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

视频汇聚平台EasyCVR视频广场侧边栏支持拖拽

为了提升用户体验以及让平台的操作更加符合用户使用习惯&#xff0c;我们在EasyCVR v3.3版本中&#xff0c;支持面包屑侧边栏的广场视频、分组列表、收藏这三个模块拖拽排序&#xff0c;并且该操作在视频广场、视频调阅、电子地图、录像回放等页面均能支持。 TSINGSEE青犀视频…

服务器运行python程序的使用说明

服务器的使用与说明 文章目录 服务器的使用与说明1.登录2.Python的使用2.1 服务器已安装python32.2 往自己的用户目录安装python31.首先下载安装包2.解压缩3.编译与安装 2.3 新建环境变量2.4 测试 3 创建PBS作业并提交 1.登录 windowsr打开运行命令窗口&#xff0c;在运行框中…

【万字长文】SpringBoot整合Atomikos实现多数据源分布式事务(提供Gitee源码)

前言&#xff1a;在最近的实际开发的过程中&#xff0c;遇到了在多数据源的情况下要保证原子性的问题&#xff0c;这个问题当时遇到了也是思考了一段时间&#xff0c;后来通过搜集大量资料与学习&#xff0c;最后是采用了分布式事务来解决这个问题&#xff0c;在讲解之前&#…

puppeteer监听response并封装为express服务调用

const express require(express); const puppeteer require(puppeteer); const app express(); let browser; // 声明一个全局变量来存储浏览器实例app.get(/getInfo, async (req, res) > {try {const page_param req.query.page; // 获取名为"page"的查询参数…

接口测试之文件上传

在日常工作中&#xff0c;经常有上传文件功能的测试场景&#xff0c;因此&#xff0c;本文介绍两种主流编写上传文件接口测试脚本的方法。 首先&#xff0c;要知道文件上传的一般原理&#xff1a;客户端根据文件路径读取文件内容&#xff0c;将文件内容转换成二进制文件流的格式…

Gson:解析JSON为复杂对象:TypeToken

需求 通过Gson&#xff0c;将JSON字符串&#xff0c;解析为复杂类型。 比如&#xff0c;解析成如下类型&#xff1a; Map<String, List<Bean>> 依赖&#xff08;Gson&#xff09; <dependency><groupId>com.google.code.gson</groupId><art…

MyBatis查询数据库之一(概念+创建项目+基础交互)

目录 1.MyBatis是什么&#xff1f; 2.为什么学习MyBatis&#xff1f; 3. 怎么学 MyBatis 4.第⼀个MyBatis查询 4.1 添加MyBatis框架支持 4.1.1老项目添加MyBatis 4.1.2 新项目添加MyBatis 4.2 配置连接字符串和MyBatis 4.2.1 配置连接字符串 4.2.2 配置 MyBatis 中的…

eNSP:ospf和mgre的配置

实验要求&#xff1a; 第一步&#xff1a;路由、IP的配置 r1&#xff1a; <Huawei>sys Enter system view, return user view with CtrlZ. [Huawei]sys r1 [r1]int loop0 [r1-LoopBack0]ip add 192.168.1.1 24 [r1-LoopBack0]int g0/0/0 [r1-GigabitEthernet0/0/0]ip a…

Golang之路---04 并发编程——信道/通道

信道/通道 如果说 goroutine 是 Go语言程序的并发体的话&#xff0c;那么 channel&#xff08;信道&#xff09; 就是 它们之间的通信机制。channel&#xff0c;是一个可以让一个 goroutine 与另一个 goroutine 传输信息的通道&#xff0c;我把他叫做信道&#xff0c;也有人将…

基于STM32CubeMX和keil采用通用定时器中断实现固定PWM可调PWM波输出分别实现LED闪烁与呼吸灯

文章目录 前言1. PWM波阐述2. 通用定时器2.1 为什么用TIM142.2 TIM14功能介绍2.3 一些配置参数解释2.4 PWM实现流程&中断2.4.1 非中断PWM输出(LED闪烁)2.4.2 中断PWM输出(LED呼吸灯) 3. STM32CubeMX配置3.1 GPIO配置3.2 时钟配置3.3 定时器相关参数配置3.4 Debug配置3.5 中…

C# Blazor 学习笔记(11):路由跳转和信息传值

文章目录 前言路由跳转测试用例路由传参/路由约束想法更新&#xff1a;2023年8月4日 前言 Blazor对路由跳转进行了封装。 ASP.NET Core Blazor 路由和导航 NavigationManager 类 本文的主要内容就是全局的跳转 路由跳转 路由跳转就要用到NavigationManager 类。 其实最常用…

【腾讯云Cloud Studio实战训练营】使用React快速构建点餐H5

文章目录 前言一、Cloud Studio是什么二、Cloud Studio特点三、Cloud Studio使用1.访问官网2.账号注册3.模板选择4.模板初始化5.H5开发安装 antd-mobile安装 Less安装 normalize&#xff1a;上传项目需要的素材&#xff1a;替换App.js主文件&#xff1a;项目启动、展示 6.发布仓…

K8s中的Secret

Secret作用&#xff1a;加密数据存在etcd里面&#xff0c;让pod容器以挂载Volume方式进行访问。场景&#xff1a;凭据

数据集相关网站(Open datasets and sources)

数据集相关网站(Open datasets and sources&#xff09; 数据集网站 Open datasets and sources政府数据网站 Government Data:金融数据网站 Financial Data Sources:犯罪数据网站 Crime Data:健康数据网站 Health Data:学术和商业数据网站 Academic and Business Data:其他数据…

用C语言构建一个数字识别卷积神经网络

卷积神经网络的具体原理和对应的python例子参见末尾的参考资料2.3. 这里仅叙述卷积神经网络的配置, 其余部分不做赘述&#xff0c;构建和训练神经网络的具体步骤请参见上一篇: 用C语言构建一个手写数字识别神经网路 卷积网络同样采用简单的三层结构&#xff0c;包括输入层con…

最新2024届【海康威视】内推码【GTK3B6】

最新2024届【海康威视】内推码【GTK3B6】 【内推码使用方法】 1.请学弟学妹们登录校招官网&#xff0c;选择岗位投递简历&#xff1b; 2.投递过程中填写内推码完成内推步骤&#xff0c;即可获得内推特权。 内推码&#xff1a;GTK3B6 内推码&#xff1a;GTK3B6 内推码&…

01背包笔记

01背包题目链接 题意&#xff1a;有一个容量为m的背包以及n个可以拿的物品&#xff0c;给出n个物品的体积和价值&#xff0c;要求输出可以拿的最大价值 思路&#xff1a;代表在前i件物品中拿取总体积不超过j的最大价值 由此可以分情况讨论状态转移 当j<v[i]时&#xff0c;说…

STM32(HAL)串口中断接收

目录 1、简介 2 基础配置 2.1.1 SYS配置 2.1.2 RCC配置 2.2 串口外设配置 2.3 项目生成 3、KEIL端程序整合 1、简介 本文对HAL串口中断函数进行介绍。 2 基础配置 2.1.1 SYS配置 2.1.2 RCC配置 2.2 串口外设配置 2.3 项目生成 3、KEIL端程序整合 首先在main.c文件中进行…

【Spring】Spring之循环依赖底层源码解析

什么是循环依赖 A依赖了B&#xff0c;B依赖了A。 示例&#xff1a; // A依赖了B class A{public B b; }// B依赖了A class B{public A a; }其实&#xff0c;循环依赖并不是问题&#xff0c;因为对象之间相互依赖是很正常的事情。示例&#xff1a; A a new A(); B b new B…