容斥原理的并
文章目录
- 简介
- 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+S3−S1∩S2−S1∩S3−S2∩S3+S1∩S2∩S3
我们可以把这个式子推导到 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 简介 推荐题解:https://www.acwing.com/solution/content/126553/ 画了图,清晰易懂,懒得打字了。 总之就是以下公式: 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)、新建一个empty activity项目,切换到project视图: 2)、修改app\src\main\res\layout\activity_main.xml文件,修改后如下: <?xml version"1.0" encoding"utf-8"?> <andr…...
gitee提交代码步骤介绍(含git环境搭建)
1、gitee官网地址 https://gitee.com; 2、Windows中安装git环境 参考博客:《Windows中安装Git软件和TortoiseGit软件》; 3、设置用户名和密码 这里的用户名和密码就是登录gitee网站的用户名和密码如果设置错误,可以在Windows系统的“凭据管理…...
【MyBatis-Plus】常用的插件介绍(乐观锁、逻辑删除、分页)
🥳🥳Welcome Huihuis Code World ! !🥳🥳 接下来看看由辉辉所写的关于MyBatis-Plus的相关操作吧 目录 🥳🥳Welcome Huihuis Code World ! !🥳🥳 一.为什么要使用MyBatis-Plus中的插…...
DApp测试网络Ganache本地部署并实现远程连接
文章目录 前言1. 安装Ganache2. 安装cpolar3. 创建公网地址4. 公网访问连接5. 固定公网地址 前言 Ganache 是DApp的测试网络,提供图形化界面,log日志等;智能合约部署时需要连接测试网络。 Ganache 是一个运行在本地测试的网络,通过结合cpol…...
好用的硬盘分区工具,傲梅分区助手 V10.2
傲梅分区助手软件可以帮助用户在硬盘上创建、调整、合并、删除分区,以及管理磁盘空间等操作。它可以帮助你进行硬盘无损分区操作。 支持系统 目前这款软件支持 Windows 7、Windows 8、Windows 10、Windows 11 等个人系统,还支持 Windows 2012/2016/2019…...
【华为鸿蒙系统学习】- HarmonyOS4.0开发|自学篇
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:"没有罗马,那就自己创造罗马~" 目录 HarmonyOS 4.0 技术介绍: HarmonyOS三大特征: 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颜色表示法以及部分理论知识 🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁 🍉博主收将持续更新学习记录获,友友们有任何问题可以…...
Openwrt源码下载出现“The remote end hung up unexpected”
最近项目原因需要下载openwrt21.02版本源码,花费了很多时间,找到正确方法后,发现可以节省很多时间,记录下过程,方便自己,可能方便他人。 一.问题阐述 openwrt21.02下载链接如下: git clone -…...
Spring定时任务动态更改(增、删、改)Cron表达式方案实例详解
Spring定时任务动态更改(增、删、改)Cron表达式方案实例详解 最近在做一个需求,用户可以在平台上配置任务计划数据(就是任务的执行和描述的相关信息,包括任务参数、cron表达式),配置后…...
常用登录加密之Shiro与Spring Security的使用对比
Shiro与Spring Security都是主流的身份认证和权限控制安全框架,Shiro偏向于前后端不分离平台,而Spring Security更偏向于前后端分离平台。接下来简单列一下两种登录验证的执行流程和示例,了解实际运用中的登录执行流程,然后重点剖…...
获取文件路径里的文件名(不包含扩展名)
“./abc/abc/llf.jpg” 写一个代码,让我获得“llf”这段字符串 import osfile_path "./abc/abc/llf.jpg" file_name os.path.splitext(os.path.basename(file_path))[0] print(file_name)在这个代码中,我们使用了os.path模块来处理文件路径…...
HiveSql语法优化二 :join算法
Hive拥有多种join算法,包括Common Join,Map Join,Bucket Map Join,Sort Merge Buckt Map Join等,下面对每种join算法做简要说明: Common Join Common Join是Hive中最稳定的join算法,其通过一个M…...
Leetcode—459.重复的子字符串【简单】
2023每日刷题(五十九) Leetcode—459.重复的子字符串 算法思想 巧解的算法思想 实现代码 从第一个位置开始到s.size()之前,看s字符串是否是ss的子串 class Solution { public:bool repeatedSubstringPattern(string s) {return (s s).fin…...
Mac安装Typora实现markdown自由
一、什么是markdown Markdown 是一种轻量级标记语言,创始人为约翰格鲁伯(John Gruber)。 它允许人们使用易读易写的纯文本格式编写文档,然后转换成有效的 XHTML(或者HTML)文档。这种语言吸收了很多在电子邮…...
前后端传参格式
前端发送 Serialize()方法 是指将一个抽象的JavaScript对象(数据结构)转换成字符串。这个字符串可以利用标准格式发送到服务器,被视为URL查询字符串或者POST数据,或者由于复杂的AJAX请求。这个方法使用的数据结构可以是JavaScri…...
【后端学前端】第三天 css动画 动态搜索框(定位、动态设置宽度)
1、学习信息 视频地址:css动画 动态搜索框(定位、动态设置宽度)_哔哩哔哩_bilibili 2、源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>test3</title>…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
