当前位置: 首页 > news >正文

容斥原理的并

文章目录

  • 简介
  • AcWing 890. 能被整除的数
    • 思路解析
    • CODE



简介

推荐题解:https://www.acwing.com/solution/content/126553/
画了图,清晰易懂,懒得打字了。
总之就是以下公式: S = S 1 + S 2 + S 3 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 3 \begin{align*} S = & S_1 + S_2 + S_3 \\ & - S_1 \cap S_2 - S_1 \cap S_3 - S_2 \cap S_3 \\ & + S_1 \cap S_2 \cap S_3 \end{align*} S=S1+S2+S3S1S2S1S3S2S3+S1S2S3
我们可以把这个式子推导到 n n n 维,奇加偶减。


AcWing 890. 能被整除的数

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

思路解析

筛出一个数的倍数,两个数的倍数 … n n n 个数的倍数,这就抽象成了 n n n 个集合的问题了。

那么如何表示选取哪几个集合(质数)呢?

  • 1 1 1 开始枚举到 n n n,将每个数看成二进制形式,如果说第 k k k 位是 1 1 1,那么就代表选第 k k k 个集合,反之不选。

如何知道被整除的数的个数?公式: n / p n / p n/p 下取整即可。

最后判断是奇数个还是偶数个,这个判断利用了二进制的一个性质:除了 2 0 2^0 20,其他所有位的和都是 2 2 2 的整数倍,所以说看是否为奇数就看它二进制最后一位是否为 1 1 1


CODE

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;  // 定义长整型别名为llconst int N = 20;  // 定义常量N为20
int n, m;  // 定义整型变量n和m
int p[N];  // 定义整型数组p,大小为Nint main(){scanf("%d%d", &n, &m);  	// 从输入中读取两个整数n和mfor(int i = 0; i < m; ++i) scanf("%d", &p[i]);  // 从输入中读取m个整数到数组p中int res = 0;  	// 初始化结果为0for(int i = 1; i < (1 << m); ++i){  // 遍历所有的子集int s = 0, t = 1;  	// 初始化s和tfor(int j = 0; j < m; ++j){  	// 遍历每一位if(i >> j & 1){  	// 如果第j位为1if((ll)t * p[j] > n){  	// 如果t乘以p[j]大于nt = -1;  	// 将t设置为-1break;  	// 跳出循环}t *= p[j];  // 更新ts++;  // 增加s}}if(t == -1) continue;  	// 如果t为-1,跳过当前循环if(s & 1) res += n / t;  // 如果s为奇数,增加n/t到reselse res -= n / t;  	// 否则,从res中减去n/t}cout << res << endl;  // 输出结果
}

相关文章:

容斥原理的并

文章目录 简介AcWing 890. 能被整除的数思路解析CODE 简介 推荐题解&#xff1a;https://www.acwing.com/solution/content/126553/ 画了图&#xff0c;清晰易懂&#xff0c;懒得打字了。 总之就是以下公式&#xff1a; S S 1 S 2 S 3 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 2 …...

JavaSE第7篇:封装

文章目录 一、封装1、好处:2、使用 二、四种权限修饰符三、构造器1、作用2、说明3、属性赋值的过程 一、封装 封装就是将类的属性私有化,提供公有的方法访问私有属性 不对外暴露打的私有的方法 单例模式 1、好处: 1.只能通过规定的方法来访问数据 2.隐藏类的实例细节,方便…...

mysql数据库相关知识【MYSQL】

mysql数据库相关知识【MYSQL】 一. 库1.1 登录数据库管理系统1.2 什么是数据库1.2.1 mysqld与mysql 1.3 编码集和校验集1.3.1 什么是编码集和校验集1.3.2 查看库对应的编码集和校验集1.3.3 用指定的编码集和校验集 1.4 库的操作 一. 库 1.1 登录数据库管理系统 这个算是第一个…...

android studio 创建按钮项目

1&#xff09;、新建一个empty activity项目&#xff0c;切换到project视图&#xff1a; 2&#xff09;、修改app\src\main\res\layout\activity_main.xml文件&#xff0c;修改后如下&#xff1a; <?xml version"1.0" encoding"utf-8"?> <andr…...

gitee提交代码步骤介绍(含git环境搭建)

1、gitee官网地址 https://gitee.com; 2、Windows中安装git环境 参考博客&#xff1a;《Windows中安装Git软件和TortoiseGit软件》&#xff1b; 3、设置用户名和密码 这里的用户名和密码就是登录gitee网站的用户名和密码如果设置错误&#xff0c;可以在Windows系统的“凭据管理…...

【MyBatis-Plus】常用的插件介绍(乐观锁、逻辑删除、分页)

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于MyBatis-Plus的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.为什么要使用MyBatis-Plus中的插…...

DApp测试网络Ganache本地部署并实现远程连接

文章目录 前言1. 安装Ganache2. 安装cpolar3. 创建公网地址4. 公网访问连接5. 固定公网地址 前言 Ganache 是DApp的测试网络&#xff0c;提供图形化界面&#xff0c;log日志等&#xff1b;智能合约部署时需要连接测试网络。 Ganache 是一个运行在本地测试的网络,通过结合cpol…...

好用的硬盘分区工具,傲梅分区助手 V10.2

傲梅分区助手软件可以帮助用户在硬盘上创建、调整、合并、删除分区&#xff0c;以及管理磁盘空间等操作。它可以帮助你进行硬盘无损分区操作。 支持系统 目前这款软件支持 Windows 7、Windows 8、Windows 10、Windows 11 等个人系统&#xff0c;还支持 Windows 2012/2016/2019…...

【华为鸿蒙系统学习】- HarmonyOS4.0开发|自学篇

​ &#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 &#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 HarmonyOS 4.0 技术介绍&#xff1a; HarmonyOS三大特征&#xff1a; 1.实现硬件互助&#…...

Qt图像处理-Qt中配置OpenCV打开本地图片

本文讲解Qt中配置OpenCV过程并用实例展示如何使用OpenCV打开图片(windows环境下) 一、下载OpenCv 本文使用版本OpenCV-MinGW-Build-OpenCV-3.4.5 下载地址: https://codeload.github.com/huihut/OpenCV-MinGW-Build/zip/refs/heads/OpenCV-3.4.5 点击Code-local-Downlo…...

HTML中RGB颜色表示法和RGBA颜色表示法

Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍HTML中RGB颜色表示法和RGBA颜色表示法以及部分理论知识 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主收将持续更新学习记录获&#xff0c;友友们有任何问题可以…...

Openwrt源码下载出现“The remote end hung up unexpected”

最近项目原因需要下载openwrt21.02版本源码&#xff0c;花费了很多时间&#xff0c;找到正确方法后&#xff0c;发现可以节省很多时间&#xff0c;记录下过程&#xff0c;方便自己&#xff0c;可能方便他人。 一.问题阐述 openwrt21.02下载链接如下&#xff1a; git clone -…...

Spring定时任务动态更改(增、删、改)Cron表达式方案实例详解

Spring定时任务动态更改&#xff08;增、删、改&#xff09;Cron表达式方案实例详解 最近在做一个需求&#xff0c;用户可以在平台上配置任务计划数据&#xff08;就是任务的执行和描述的相关信息&#xff0c;包括任务参数、cron表达式&#xff09;&#xff0c;配置后&#xf…...

常用登录加密之Shiro与Spring Security的使用对比

Shiro与Spring Security都是主流的身份认证和权限控制安全框架&#xff0c;Shiro偏向于前后端不分离平台&#xff0c;而Spring Security更偏向于前后端分离平台。接下来简单列一下两种登录验证的执行流程和示例&#xff0c;了解实际运用中的登录执行流程&#xff0c;然后重点剖…...

获取文件路径里的文件名(不包含扩展名)

“./abc/abc/llf.jpg” 写一个代码&#xff0c;让我获得“llf”这段字符串 import osfile_path "./abc/abc/llf.jpg" file_name os.path.splitext(os.path.basename(file_path))[0] print(file_name)在这个代码中&#xff0c;我们使用了os.path模块来处理文件路径…...

HiveSql语法优化二 :join算法

Hive拥有多种join算法&#xff0c;包括Common Join&#xff0c;Map Join&#xff0c;Bucket Map Join&#xff0c;Sort Merge Buckt Map Join等&#xff0c;下面对每种join算法做简要说明&#xff1a; Common Join Common Join是Hive中最稳定的join算法&#xff0c;其通过一个M…...

Leetcode—459.重复的子字符串【简单】

2023每日刷题&#xff08;五十九&#xff09; Leetcode—459.重复的子字符串 算法思想 巧解的算法思想 实现代码 从第一个位置开始到s.size()之前&#xff0c;看s字符串是否是ss的子串 class Solution { public:bool repeatedSubstringPattern(string s) {return (s s).fin…...

Mac安装Typora实现markdown自由

一、什么是markdown Markdown 是一种轻量级标记语言&#xff0c;创始人为约翰格鲁伯&#xff08;John Gruber&#xff09;。 它允许人们使用易读易写的纯文本格式编写文档&#xff0c;然后转换成有效的 XHTML&#xff08;或者HTML&#xff09;文档。这种语言吸收了很多在电子邮…...

前后端传参格式

前端发送 Serialize()方法 是指将一个抽象的JavaScript对象&#xff08;数据结构&#xff09;转换成字符串。这个字符串可以利用标准格式发送到服务器&#xff0c;被视为URL查询字符串或者POST数据&#xff0c;或者由于复杂的AJAX请求。这个方法使用的数据结构可以是JavaScri…...

【后端学前端】第三天 css动画 动态搜索框(定位、动态设置宽度)

1、学习信息 视频地址&#xff1a;css动画 动态搜索框&#xff08;定位、动态设置宽度&#xff09;_哔哩哔哩_bilibili 2、源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>test3</title>…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...