笔记---容斥原理

AcWing,890.能被整除的数
给定一个整数 n n n m m m 个不同的质数 p 1 , p 2 , … , p m p_{1},p_{2},…,p_{m} p1,p2,,pm

请你求出 1 ∼ n 1∼n 1n 中能被 p 1 , p 2 , … , p m p_{1},p_{2},…,p_{m} p1,p2,,pm 中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数 n n n m m m

第二行包含 m m m 个质数。

输出格式
输出一个整数,表示满足条件的整数的个数。

数据范围
1 ≤ m ≤ 16 , 1 ≤ n , p i ≤ 109 1≤m≤16,1≤n,p_{i}≤109 1m16,1n,pi109

输入样例:

10 2
2 3

输出样例:

7

容斥原理:
假如我们现在有一个韦恩图,如果要不重不漏的表示出整个集合的面积(即三个集合的元素个数):

在这里插入图片描述

这就是一个基础的容斥原理,推广到n个圆的维恩图的话:
1个圆自己的-每2个圆相交的+有3个圆相交的-有4个圆相交的+…
且观察可知选偶数个集合的时候是负的,而选奇数个集合时是正的

对于这道题,我们要求个数时,就可以用 S 1 S_{1} S1表示1到n中能被 p 1 p_{1} p1整除的数,然后 S 2 S_{2} S2表示1到n中能被 p 2 p_{2} p2整除的数…让我们求个数的时候,就可以用容斥原理来求

S p S_{p} Sp表示1到n中能被p整除的个数,即是p的倍数的个数有多少,那么 S p = [ n p ] S_{p}=[\frac{n}{p}] Sp=[pn]

有多个集合相交的部分,即求能够被 p 1 , p 2 , p 3 . . . p_{1},p_{2},p_{3}... p1,p2,p3...等整除的数有多少时,表示为[ n p 1 ∗ p 2 ∗ . . . ∗ p k \frac{n}{p_{1}*p_{2}*...*p_{k}} p1p2...pkn]

为什么下取整? 因为有时候n可能不能整除p,则下取整可以保证取到最大的那个与p成倍数的数

用二进制数和位运算方法来枚举选法,从1枚举到2n,用每一位是1还是0来代表选法

此处容斥原理体现为:这里选的每一个数都相当于一个小集合,集合数代表的便是选的数的个数
代码:

#include<iostream>
using namespace std;
const int N = 20;

int n, m;
int p[N];

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> p[i];	//读入质数

	int res = 0;
	for (int i = 1; i < 1 << m; i++) {	//从1枚举到2的m次方-1个选法

		int t = 1, cnt = 0;	//t表示当前质数的乘积,cnt表示集合个数

		for(int j = 0;j < m;j++)	//枚举m个质数
			if (i >> j & 1) {	//如果当前这一位是1,即选上了
				cnt++;	//集合数加1

				//如果按i这种选法乘过之后,发现大于n了,那么就代表这种选法不成立
				//在这个情况下无法实现被这些选上的质数整除
				//相反如果乘过这些质数后小于n,那么就说明这些数是可以把1到n中的数整除的
				if ((long long)t * p[j] > n) {	//如果大于n就不用算了
					t = -1;
					break;
				}
				t *= p[j];
			}

		if (t != -1) {	//如果没有大于n
			if (cnt % 2) res += n / t;	//如果有奇数个集合那么加上
			else res -= n / t;			//如果有偶数个集合那么减去
		}
	}
	cout << res << endl;

	return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SemiDrive E3 MCAL 开发系列(1) – 环境搭建

一、 概述 本文将会介绍 SemiDrive E3 系列 MCU 的MCAL 开发环境搭建&#xff0c;包括如何获取及安装 EB 和 MCAL&#xff0c;E3 Gateway 开发板介绍&#xff0c;MCAL 工程的编译、下载等。 二、 EB 和 MCAL 的获取及安装 2.1 软件获取 EB Tresos 是用于进行 MCAL 配置…

Android Split APK介绍

文章目录 Split APKSplit APK 详细介绍概念Android App Bundle&#xff08;AAB&#xff09;Split APK 的优势动态分发减小安装包大小模块化和渠道分发 Split APK 的类型基于屏幕密度### 基于 CPU 架构基于语言 实现 Split APK Split APK Split APK 是 Android 中一种应用程序安…

【测试运维】web自动化全知识点笔记第1篇:什么是Web自动化测试(已分享,附代码)

本系列文章md笔记&#xff08;已分享&#xff09;主要讨论Web自动化测试相关知识。了解什么是自动化&#xff0c;理解什么是自动化测试以及为什么要使用自动化测试。具体包含&#xff1a;WebDriver的基本操作&#xff0c;WebDriver的鼠标、键盘操作&#xff0c;下拉选择框、警告…

2024.2.4日总结(小程序开发1)

小程序开发和普通网页开发的区别 运行环境不同 网页运行在浏览器环境中&#xff0c;小程序运行在微信环境中 API不同 由于运行的环境不同&#xff0c;所以小程序中无法调用DCM和BOM的API&#xff0c;但是可以调用微信环境提供的各种API&#xff0c;如&#xff1a;地理定位&…

Python 数据分析(PYDA)第三版(一)

原文&#xff1a;wesmckinney.com/book/ 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 关于开放版本 第 3 版的《Python 数据分析》现在作为“开放获取”HTML 版本在此网站wesmckinney.com/book上提供&#xff0c;除了通常的印刷和电子书格式。该版本最初于 2022 年…

微服务基础(持续更新中)

安装SSH以及虚拟机&#xff0c;Centos具体步骤见 https://b11et3un53m.feishu.cn/wiki/FJAnwOhpIihMkLkOKQocdWZ7nUc

vulhub中Adminer ElasticSearch 和 ClickHouse 错误页面SSRF漏洞复现(CVE-2021-21311)

Adminer是一个PHP编写的开源数据库管理工具&#xff0c;支持MySQL、MariaDB、PostgreSQL、SQLite、MS SQL、Oracle、Elasticsearch、MongoDB等数据库。 在其4.0.0到4.7.9版本之间&#xff0c;连接 ElasticSearch 和 ClickHouse 数据库时存在一处服务端请求伪造漏洞&#xff08…

202416读书笔记|《总有人会拥抱满身带刺的你》——今天我请客,想请你快乐

202416读书笔记|《总有人会拥抱满身带刺的你》——今天我请客&#xff0c;想请你快乐 这是一篇暖萌轻松的绘本推荐记录书评&#xff0c;《总有人会拥抱满身带刺的你》纳米著&#xff0c;《今天我请客&#xff0c;想请你快乐》燕七著&#xff0c;都还不错&#xff0c;截取摘录了…

从搜索引擎到答案引擎:LLM驱动的变革

在过去的几周里&#xff0c;我一直在思考和起草这篇文章&#xff0c;认为谷歌搜索正处于被颠覆的边缘&#xff0c;它实际上可能会影响 SEO 作为业务牵引渠道的可行性。 考虑到谷歌二十多年来的完全统治地位&#xff0c;以及任何竞争对手都完全无力削弱它&#xff0c;坦率地说&…

解析 JavaScript 异步编程:从回调地狱到 Promise 和 Async/Await

在现代的JavaScript开发中&#xff0c;处理异步任务变得愈发重要&#xff0c;因为它们允许我们在等待I/O、网络请求或定时器等事件时继续执行其他任务&#xff0c;以提高程序的性能和响应能力。本文将介绍JavaScript中异步编程的演变过程&#xff0c;从最初的回调地狱到后来的P…

【数据结构与算法】(9)基础数据结构 之 阻塞队列的单锁实现、双锁实现详细代码示例讲解

目录 2.8 阻塞队列1) 单锁实现2) 双锁实现 2.8 阻塞队列 之前的队列在很多场景下都不能很好地工作&#xff0c;例如 大部分场景要求分离向队列放入&#xff08;生产者&#xff09;、从队列拿出&#xff08;消费者&#xff09;两个角色、它们得由不同的线程来担当&#xff0c;…

使用绿联私有云Docker搭建自动化实时网页监控工具,实现降价提醒/RSS监控等

使用绿联私有云Docker搭建自动化实时网页监控工具&#xff0c;实现降价提醒/RSS监控等 哈喽小伙伴们好&#xff0c;我是Stark-C~ 之前老是有小伙伴们在评论区说我分享的Docker容器都是通过Docker run命令部署的&#xff0c;能不能照顾下像绿联私有云这种新势力NAS的新手用户&…

C# CAD界面-自定义工具栏(三)

运行环境 vs2022 c# cad2016 调试成功 一、引用 二、开发代码进行详细的说明 初始化与获取AutoCAD核心对象&#xff1a; Database db HostApplicationServices.WorkingDatabase;&#xff1a;这行代码获取当前工作中的AutoCAD数据库对象。在AutoCAD中&#xff0c;所有图形数…

【Git】01 Git介绍与安装

文章目录 一、版本控制系统二、Git三、Windows安装Git3.1 下载Git3.2 安装3.3 检查 四、Linux安装Git4.1 YUM安装4.2 源码安装 五、配置Git5.1 配置用户名和邮箱5.2 配置级别5.3 查看配置 六、总结 一、版本控制系统 版本控制系统&#xff0c;Version Control System&#xff…

【消息队列】kafka整理

kafka整理 整理kafka基本知识供回顾。

基于NSGA-II的深度迁移学习

深度迁移学习 迁移学习是一种机器学习技术&#xff0c;它允许一个预训练的模型被用作起点&#xff0c;在此基础上进行微调以适应新的任务或数据。其核心思想是利用从一个任务中学到的知识来帮助解决另一个相关的任务&#xff0c;即使这两个任务的数据分布不完全相同。这种方法…

vulnhub靶场之Thales

一.环境搭建 1.靶场描述 Description : Open your eyes and change your perspective includes 2 flags:user.txt and root.txt. Telegram: machineboy141 (for any hint) This works better with VIrtualBox rathe than VMware 2.靶场地址 https://www.vulnhub.com/entry/t…

年假作业3.0

1、选择题 BCDAA 2、填空题 15,27 15 11,10,13,12 3、改错题 1.缺少了要使用的命名空间&#xff0c;应在加上#include <iostream>的下一行添加using namespace std&#xff0c;void main(){}报错&#xff0c;C语言中main函数必须返回int改为&#xff1a;int main(…

海康IPC摄像机接入国标平台,发现一直不在线(离线)的处理方式

目 录 一、问题 二、问题分析 &#xff08;一&#xff09;常见设备离线问题的原因 &#xff08;二&#xff09;原因分析 三、问题查处 &#xff08;一&#xff09;设备端排查故障&#xff08;设备端自查&#xff09; 1、检查GB28181参数配置是否有误 2、…

vulhub中Apache APISIX Dashboard API权限绕过导致RCE(CVE-2021-45232)

Apache APISIX是一个动态、实时、高性能API网关&#xff0c;而Apache APISIX Dashboard是一个配套的前端面板。 Apache APISIX Dashboard 2.10.1版本前存在两个API/apisix/admin/migrate/export和/apisix/admin/migrate/import&#xff0c;他们没有经过droplet框架的权限验证&…