容斥原理(有求区间(1-r)里面跟n互质的个数的高效方面模板)

2024-02-14 15:48

本文主要是介绍容斥原理(有求区间(1-r)里面跟n互质的个数的高效方面模板),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

容斥原理 编辑
在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。[1]
中文名 容斥原理 外文名 Principle of inclusion-exclusion[2] 别 称 排容原理 应用学科 组合数学 计算机
目录
1 公式
2 严格证明
3 原理
公式编辑

也可表示为
设S为有限集, ,则

由于

所以

两个集合的容斥关系公式:A∪B =|A∪B| = |A|+|B| - |A∩B |(∩:重合的部分)
三个集合的容斥关系公式:|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|

详细推理如下:
1、 等式右边改造 = {[(A+B - A∩B)+C - B∩C] - C∩A }+ A∩B∩C
2、维恩图分块标记如右图图:1245构成A,2356构成B,4567构成C
3、等式右边()里指的是下图的1+2+3+4+5+6六部分:
那么A∪B∪C还缺部分7。
4、等式右边[]号里+C(4+5+6+7)后,相当于A∪B∪C多加了4+5+6三部分,
减去B∩C(即5+6两部分)后,还多加了部分4。
5、等式右边{}里减去C∩A (即4+5两部分)后,A∪B∪C又多减了部分5,
则加上A∩B∩C(即5)刚好是A∪B∪C。
严格证明编辑
对于容斥原理我们可以利用数学归纳法证明:
证明:当 时,等式成立(证明略)。
假设 时结论成立,则当 时,

所以当 时,结论仍成立。因此对任意 ,均可使所证等式成立。[1]
原理编辑
如果被计数的事物有A、B两类,那么,A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。(A∪B = A+B - A∩B)
例1 一次期末考试,某班有15人数学得满分,有12人语文得满分,并且有4人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?
分析
依题意,被计数的事物有语、数得满分两类,“数学得满分”称为“A类元素”,“语文得满分”称为“B类元素”,“语、数都是满分”称为“既是A类又是B类的元素”,“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。
答案
15+12-4=23
试一试
电视台向100人调查前一天收看电视的情况,有62人看过2频道,34人看过8频道,其中11人两个频道都看过。两个频道都没看过的有多少人?
100-(62+34-11)=15
中学教科书给出的定义
如果被计数的事物有A、B、C三类,那么,A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。(A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C)[1]
例1(小学奥数题)
某校六⑴班有学生45人,每人在暑假里都参加体育训练队,其中参加足球队的有25人,参加排球队的有22人,参加游泳队的有24人,足球、排球都参加的有12人,足球、游泳都参加的有9人,排球、游泳都参加的有8人,问:三项都参加的有多少人?
分析:参加足球队的人数25人为A类元素,参加排球队人数22人为B类元素,参加游泳队的人数24人为C类元素,既是A类又是B类的为足球排球都参加的12人,既是B类又C类的为足球游泳都参加的9人,既是C类又是A类的为排球游泳都参加的8人,三项都参加的是A类B类C类的总和设为X。注意:这个题说的每人都参加了体育训练队,所以这个班的总人数即为A类B类和C类的总和。
答案:25+22+24-12-9-8+X=45 ,解得X=3[3]
例2(高中题)
在1到1000的自然数中,能被3或5整除的数共有多少个?不能被3或5整除的数共有多少个?
分析:显然,这是一个重复计数问题(当然,如果不怕麻烦你可以分别去数3的倍数,5的倍数)。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素,能“同时被3或5整除的数(15的倍数)”就是被重复计算的数,即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。我们还不能直接计算,必须先求出所需条件。1000÷3=333……1,能被3整除的数有333个(想一想,这是为什么?)同理,可以求出其他的条件。
例3(高中题)
分母是1001的最简分数一共有多少个?
分析:这一题实际上就是找分子中不能与1001进行约分的数。由于1001=7×11×13,所以就是找不能被7,11,13整除的数。
解答:1~1001中,有7的倍数1001/7 = 143 (个);有11的倍数1001/11 = 91 (个),有13的倍数1001/13 = 77 (个);有7*11=77;77是11的倍数1001/77 = 13 (个),有7*13=91;91是13的倍数;1001/91 = 11 (个),有11*13=143;143是13的倍数1001/143 = 7 (个).有1001的倍数1个。
由容斥原理知:在1~1001中,能被7或11或13整除的数有(143+91+77)-(13+11+7)+1=281(个),从而不能被7、11或13整除的数有1001-281=720(个).也就是说,分母为1001的最简分数有720个。
例4(小学奥数题)
某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后,有4名学生在这三个项目上都没有达到优秀,其余每人至少有一项达到了优秀,达到了优秀的这部分学生情况如下表:
短跑
游泳
投掷
短跑
游泳
短跑
投掷
游泳
投掷
短跑
游泳
投掷
1 7
1 8
1 5
6
6
5
2
求这个班的学生共有多少人?
分析:这个班的学生数,应包括达到优秀和没有达到优秀的。
4+17+18+15-6-6-5+2=39(人)
试一试:一个班有42人,参加合唱队的有30人,参加美术组的有25人,有5人什么都没有参加,求两种都参加的有多少人?
(30+25+5)-42=18(人)[3]
例5(小学奥数题)
在一根长的木棍上有三种刻度线,第一种刻度线将木棍分成10等份,第二种将木棍分成12等份,第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断,木棍总共被锯成多少段?
分析:
很显然,要计算木棍被锯成多少段,只需要计算出木棍上共有多少条不同的刻度线,在此基础上加1就是段数了。
若按将木棍分成10等份的刻度线锯开,木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线,显然刻度线有重复的,如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线,也是如此。所以,我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢?想一想,被计数的事物有那几类?每一类的元素个数是多少?
解答
解一:[10,12,15]=60,设木棍60厘米
60÷10=6厘米,60÷12=5厘米,60÷15=4(厘米
10等分的为第一种刻度线,共10-1=9(条)
12等分的为第二种刻度线,共12-1=11(条)
15等分的为第三种刻度线,过15-1=14(条)
第一种与第二种刻度线重合的[6,5]=30,60÷30-1=2-1=1(条)
第一种与第三种刻度线重合的[6,4]=12,60÷12-1=5-1=4(条)
第二种与第三种刻度线重合的[5,4]=20,60÷20-1=3-1=2(条)
三种刻度线重合的没有,[6、5、4]=60
因此,共有刻度线9+11+14-1-4-2=27条,木棍总共被锯成27+1=28段。
解二:总长看成单位1分别分成10、12、15段。1/10与1/12的最小公倍数1/2,1/10与1/15的最小公倍数1/5,1/12与1/15的最小公倍数1/3,1/10,1/12和1/15的最小公倍数为1,有10+12+15-(2+5+3)+1=28
解三:
10、12、15的最小公倍数是60,假设木棍就是长60,
1、那么,分成10等份的每份6,刻度就是
0,6,12,18,24,30,36,42,48,54,60
2、分成12等分的每份就是5,
0,5,10,15,20,25,30,35,40,45,50,55,60
3、分成15等分的每份就是4,
0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60
4、把相同刻度的合并,就是有刻度如下:
0,4,5,6,8,10,12,15,16,18,20,24,25,28,30,32,35,36,40,42,44,45,48,50,52,54,55,56,60[3]
例6
给定r,n求[1,r]内与n互素的个数有多少个?
分析:
看到这个问题,数论有学一点的童鞋可能会想如果r = n的话,不就是欧拉函数了吗?是的,可惜这个问题的r ,n是不一定会相等的。直接求解问题就是比较复杂的。所以我们还是研究这个问题是逆问题。也就是说求gcd(k,n) >= 2,在1 - n之间k有多少个 。那么我们就可以枚举n的素因子来进行求解。

//时间复杂度O(sqrt(n))…
(注意加上头文件#include)
int solve(int r, int n)
{
vectorp;
for (int i = 2; i * i <= n; ++i){
if (n % i == 0){
p.push_back(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) p.push_back(n);
int sum = 0;
for (int S = 1; S < (1 << p.size()); ++S){
int mult = 1, bits = 0;
for (int i = 0; i < p.size(); ++i){
if (S & (1 << i)){
++bits;
mult *= p[i];
}
}
int cur = r / mult;
if (bits % 2 == 1) sum += cur;
else sum -= cur;
}
return r - sum;
}

这篇关于容斥原理(有求区间(1-r)里面跟n互质的个数的高效方面模板)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/708932

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工