【算法】求欧拉函数(包括完整的证明以及代码模板,建议收藏)
求欧拉函数
前置知识
互质:互质是公约数只有1的两个整数,叫做互质整数。
欧拉函数定义
1 ∼ N − 1 1∼N-1 1∼N−1中与N互质的数的个数被称为欧拉函数,记为 ϕ ( N ) \phi(N) ϕ(N)。
若在算数基本定理中, N = p 1 a 1 p 2 a 2 . . . p m a m N=p_1^{a_1}p_2^{a_2}...p_m^{a_m} N=p1a1p2a2...pmam,则:
ϕ ( N ) = N ⋅ p 1 − 1 p 1 ⋅ p 2 − 1 p 2 ⋅ . . . ⋅ p m − 1 p m \phi(N)=N\cdot\frac{p_1-1}{p_1}\cdot\frac{p_2-1}{p_2}\cdot...\cdot\frac{p_m-1}{p_m} ϕ(N)=N⋅p1p1−1⋅p2p2−1⋅...⋅pmpm−1
欧拉函数推导
首先我们要知道 1 , 2 , 3... N − 1 , N 1,2,3...N-1,N 1,2,3...N−1,N与 N N N互质的个数是 1 ∼ N 1∼N 1∼N数列去除N的质因子的倍数。
例如 N = 10 , 即 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 N=10,即1,2,3,4,5,6,7,8,9,10 N=10,即1,2,3,4,5,6,7,8,9,10去除 N N N的质因子的倍数 , 则 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 . ,则1,\bcancel{2},3,\bcancel{4},\bcancel{5},\bcancel{6},7,\bcancel{8},9,\bcancel{10}. ,则1,2 ,3,4 ,5 ,6 ,7,8 ,9,10 .
显然, 1 , 3 , 7 , 9 1,3,7,9 1,3,7,9与 10 10 10互质。
由上方结论使用容斥原理进行数学推导如下:
∵ N = p 1 a 1 p 2 a 2 . . . p m a m \because N=p_1^{a_1}p_2^{a_2}...p_m^{a_m} ∵N=p1a1p2a2...pmam
①.从1~n中去掉 p 1 , p 2 , . . . , p k p_1,p_2,...,p_k p1,p2,...,pk的所有倍数的个数,即
n ← n − n p 1 − n p 2 − . . . − n p k n←n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k} n←n−p1n−p2n−...−pkn
②.由容斥原理, p i ⋅ p j p_i \cdot p_j pi⋅pj的倍数个数被①减了两次,所以加上所有 p i ⋅ p j p_i\cdot p_j pi⋅pj的倍数的个数(其中 p i , p j p_i,p_j pi,pj是 p 1 ∼ p k p_1∼p_k p1∼pk的排列),即
n ← n + n p 1 ⋅ p 2 + n p 1 ⋅ p 3 + . . . + n p k − 1 ⋅ p k n←n+\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k} n←n+p1⋅p2n+p1⋅p3n+...+pk−1⋅pkn
③.减去所有 p i ⋅ p j ⋅ p k p_i\cdot p_j \cdot p_k pi⋅pj⋅pk的倍数个数,即
n ← n − n p 1 ⋅ p 2 ⋅ p 3 − n p 1 ⋅ p 2 ⋅ p 4 − . . . − n p k − 2 ⋅ p k − 1 ⋅ p k n←n-\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2 \cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k} n←n−p1⋅p2⋅p3n−p1⋅p2⋅p4n−...−pk−2⋅pk−1⋅pkn
④.同理,加上所有 p i ⋅ p j ⋅ p k ⋅ p l p_i\cdot p_j \cdot p_k \cdot p_l pi⋅pj⋅pk⋅pl的倍数个数,即
n ← n + n p 1 ⋅ p 2 ⋅ p 3 ⋅ p 4 + n p 1 ⋅ p 2 ⋅ p 3 ⋅ p 5 + . . . + n p k − 3 ⋅ p k − 2 ⋅ p k − 1 ⋅ p k n←n+\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2 \cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot {p_k}} n←n+p1⋅p2⋅p3⋅p4n+p1⋅p2⋅p3⋅p5n+...+pk−3⋅pk−2⋅pk−1⋅pkn
KaTeX parse error: Can't use function '\mathord' in text mode at position 1: \̲m̲a̲t̲h̲o̲r̲d̲{\varvdots\rule…
因此,
ϕ ( n ) = n − n p 1 − n p 2 − . . . − n p k + n p 1 ⋅ p 2 + n p 1 ⋅ p 3 + . . . + n p k − 1 ⋅ p k − n p 1 ⋅ p 2 ⋅ p 3 − n p 1 ⋅ p 2 ⋅ p 4 − . . . − n p k − 2 ⋅ p k − 1 ⋅ p k + n p 1 ⋅ p 2 ⋅ p 3 ⋅ p 4 + n p 1 ⋅ p 2 ⋅ p 3 ⋅ p 5 + . . . + n p k − 3 ⋅ p k − 2 ⋅ p k − 1 ⋅ p k − . . . \phi(n)=n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_k}\\ +\frac{n}{p_1\cdot p_2}+\frac{n}{p_1\cdot p_3}+...+\frac{n}{p_{k-1}\cdot p_k}\\ -\frac{n}{p_1\cdot p_2\cdot p_3}-\frac{n}{p_1\cdot p_2 \cdot p_4}-...-\frac{n}{p_{k-2}\cdot p_{k-1}\cdot p_k}\\ +\frac{n}{p_1\cdot p_2\cdot p_3\cdot p_4}+\frac{n}{p_1\cdot p_2 \cdot p_3\cdot p_5}+...+\frac{n}{p_{k-3}\cdot p_{k-2}\cdot p_{k-1}\cdot {p_k}}\\ -... ϕ(n)=n−p1n−p2n−...−pkn+p1⋅p2n+p1⋅p3n+...+pk−1⋅pkn−p1⋅p2⋅p3n−p1⋅p2⋅p4n−...−pk−2⋅pk−1⋅pkn+p1⋅p2⋅p3⋅p4n+p1⋅p2⋅p3⋅p5n+...+pk−3⋅pk−2⋅pk−1⋅pkn−...
也就是n减去奇数个质因子的倍数个数,加上偶数个质因子的倍数个数,循环往复。将上式等价变形,得到
ϕ ( n ) = n ⋅ ( 1 − 1 p 1 ) ⋅ ( 1 − 1 p 2 ) . . . ⋅ ( 1 − 1 p k ) \phi(n)=n\cdot(1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})...\cdot(1-\frac{1}{p_k}) ϕ(n)=n⋅(1−p11)⋅(1−p21)...⋅(1−pk1)
证必。
代码模板
int phi(int x)
{int res = x;for (int i = 2; i <= x / i; i ++ )if (x % i == 0){res = res / i * (i - 1);while (x % i == 0) x /= i;}if (x > 1) res = res / x * (x - 1);return res;
}
相关文章:
【算法】求欧拉函数(包括完整的证明以及代码模板,建议收藏)
求欧拉函数 前置知识 互质:互质是公约数只有1的两个整数,叫做互质整数。 欧拉函数定义 1 ∼ N − 1 1∼N-1 1∼N−1中与N互质的数的个数被称为欧拉函数,记为 ϕ ( N ) \phi(N) ϕ(N)。 若在算数基本定理中, N p 1 a 1 p 2 a 2 .…...
Ceph的应用
文章目录 一、创建 CephFS 文件系统 MDS 接口1)在管理节点创建 mds 服务2)查看各个节点的 mds 服务3)创建存储池,启用 ceph 文件系统4)查看mds状态,一个up,其余两个待命,目前的工作的…...
mac m1 触控栏TouchBar功能栏异常
电脑可能在高温下运行时间过长,导致TouchBar之前正常显示的调整屏幕亮度与调整声音等功能的按钮均丢失,然后看了一眼键盘设置,设置也是正常的,已勾选显示功能栏 下面请看 如何在MacBook Pro(macOS Monterey࿰…...
“奢侈品”价格的“快消品”,竹叶青这么想赚年轻人的“茶水钱”?
文 | 螳螂观察 作者 | 青月 或许是受养生焦虑的影响,这届年轻人似乎爱上了喝茶。 《抖音电商茶行业洞察报告》数据显示, 年轻客群已经成为了抖音电商茶行业的增长极,在茶叶、茶具、茶文化书籍等方面,18-30岁消费者是当之无愧消…...
【Matlab】基于随机森林算法的时间序列预测(Excel可直接替换数据)
【Matlab】基于随机森林算法的时间序列预测(Excel可直接替换数据) 1.模型原理2.数学公式3.文件结构4.Excel数据5.分块代码6.完整代码7.运行结果1.模型原理 基于随机森林算法的时间序列预测是一种利用随机森林模型来解决时间序列预测问题的方法。在传统的随机森林算法中,对于…...
vue 中断请求
1 背景:针对一些请求时间较长,组件销毁后即中断请求; 2 方法: data(){return {//用于取消请求abortController:new AbortController(), } }, created(){//请求接口this.groundAcquisition(); }, beforeDestroy(){//中断请求this.…...
Jwt(Json web token)——从Http协议到session+cookie到Token Jwt介绍 Jwt的应用:登陆验证的流程
目录 引出从Http协议到session&cookie到TokenHTTP协议session & cookiesessioncookie为什么需要session & cookie? JavaEE传统解决长连接方案问题:分布式不适用解决方案:令牌Token Jwt,Json web tokenjwt的结构Header加密算法Ba…...
Java使用 java.util.regex.Pattern 正则表达式校验参数值是否规范
场景: java中我们可以利用 Pattern 注解对某个入参进行规则校验,但有些特殊参数在接口入口处不方便校验,需要在代码中校验 一、使用 Pattern 注解校验 Pattern(regexp "^[a-zA-Z0-9]$", message "xxx号限输入字母、…...
HDFS基本操作命令
这里写目录标题 HDFS Shell CLI客户端说明常用命令hadoop fs -mkdir [-p] <path>hadoop fs -ls [-h] [-R] [<path>...]上传文件到指定目录下方法一:hadoop fs -put [-f] [-p] <localsrc>.....<dst>方法二:hadoop fs -moveFromLocal <loc…...
git 实操
首先有安装好的git,安装好后,会在任一目录下右键出现git bash和git gui两个选项 打开git bash,设置好全局变量,用户名和邮箱,设置方法为: git config -- global user.name "xxx" git config --global user.email "xxxxxx.com" 1.创建版本库 git init 命…...
Visual Studio Code Python 扩展中的包管理
排版:Alan Wang Python 凭借其简单的语法和强大的库,目前已成为最流行的编程语言之一,也是最适合那些刚接触编程的人们的语言。但是,随着项目复杂性和规模的增长,管理依赖项的复杂性也会增加。当新用户不断承接更成熟的…...
spring学习笔记九
数据源对象管理 1、加入pom坐标 <dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.1.16</version></dependency><!-- https://mvnrepository.com/artifact/c3p0/c3p0 --><depe…...
java list stream 使用
1、实现List对象集合的简单去重(distinct()) List<User> list list.stream().distinct().collect(Collectors.toList()); 2、实现List集合的根据属性(name)去重 list list.stream().filter(o -> o.getName() ! …...
两个Ubuntu电脑用SSH远程连接
两个Ubuntu电脑用SSH远程连接 1.ssh客户端及服务端的安装: 打开终端后,只需要以下两个命令即可 sudo apt-get install openssh-clientsudo apt-get install openssh-server2.启动ssh服务,执行以下命令: sudo /etc/init.d/ssh …...
讲解 @ServletComponentScan注解
目录: 1、用法介绍2、实例讲解 1、介绍 在SpringBoot项目启动器中添加ServletComponentScan注解后,SpringBoot在启动时会扫描并注册所有带有WebServlet(控制器)、WebFilter(过滤器)、WebListener(监听器&a…...
20款奔驰S350商务型加装原厂前排座椅通风系统,夏天必备的功能
通风座椅的主动通风功能可以迅速将座椅表面温度降至适宜程度,从而确保最佳座椅舒适性。该功能启用后,车内空气透过打孔皮饰座套被吸入座椅内部,持续时间为 8 分钟。然后,风扇会自动改变旋转方向,将更凉爽的环境空气从座…...
Rust vs Go:常用语法对比(十一)
题目来自 Rust Vs Go: Which Language Is Better For Developing High-Performance Applications?[1] 202. Sum of squares Calculate the sum of squares s of data, an array of floating point values. 计算平方和 package mainimport ( "math")func main() { da…...
Spring MVC拦截器和跨域请求
一、拦截器简介 SpringMVC的拦截器(Interceptor)也是AOP思想的一种实现方式。它与Servlet的过滤器(Filter)功能类似,主要用于拦截用户的请求并做相应的处理,通常应用在权限验证、记录请求信息的日志、判断用…...
C++初阶--C++入门
目录 前言C关键字命名空间命名空间的定义命名空间的使用加命名空间名称及作用域限定符使用using namespace 命名空间名称引入使用using将命名空间中的成员引入 C的输入与输出缺省参数全缺省半缺省参数 函数重载参数类型不同参数个数不同参数类型顺序不同 引用引用特性 常引用使…...
Matlab实现PID控制仿真(附上30个完整仿真源码+数据)
本文介绍了如何使用Matlab实现PID控制器的仿真。首先,我们将简要介绍PID控制器的原理和控制算法。然后,我们将使用Matlab编写一个简单的PID控制器,并使用仿真环境来验证其性能。最后,我们将通过调整PID控制器的参数来优化控制系统…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
