【算法】求欧拉函数(包括完整的证明以及代码模板,建议收藏)
求欧拉函数
前置知识
互质:互质是公约数只有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控制器的参数来优化控制系统…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...

Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...