算法学习——GCD与欧拉函数
欧几里得GCD:
GCD算法是使用辗转相除法求最大公因数的算法,简单而言就是gcd(a,b) = gcd(b,a mod b)
递归写法:
int Gcd(int a, int b)
{if(b == 0)return a;return Gcd(b, a % b);
}
迭代写法:
int Gcd(int a, int b)
{while(b != 0){int r = b;b = a % b;a = r;}return a;
}
欧拉函数:
欧拉函数Euler(n):表示不大于n且与n互质的正整数的个数。
由唯一分解定理,n=p1^k1*p2^k2*...*pn^km,pi均为质数,ki是其幂次。
由此可推出欧拉函数的求法:Euler(n)=n/p1*(p1-1)/p2*(p2-1)/.../pn*(pn-1)
上面的公式该怎么理解呢?
让我们看看GPT怎么说

也就是说最终的目的就是去除掉所有质因数。上式中的1/pi*(pi-1) == (1- 1/pi),本质一样。
代码:
ull Euler(ull n)//求n的欧拉函数(固定模板)
{ull phi=n;for(int i=2;i*i<=n;i++)//枚举n的质因数 {if(n%i)continue;while(n%i==0)//i是质因数 {n=n/i;//n不断除以i直至i不再是n的质因数 }phi=phi/i*(i-1);//递推欧拉函数,Euler(n)=n/pi*(pi-1) } //最后可能还剩下一个大于n的因子,如12=2*2*3,最后将剩下3,补充上 if(n>1)phi=phi/n*(n-1);return phi;
}
我们简单解释下这个代码。根据上面的结论,如果 p 为素数,n 是 p 的正整数次方,那么Euler(n) = n * (1 - 1/p)。所以phi=phi/i*(i-1);就是在求每个质因子带来的互质数的个数。而while循环则是在不断的改变n,因为我们每次迭代一个因子的同时,我们在计算完phi后要消除这个质因子在n中的影响,所以我们通过while循环不断除以这个因子。
为什么是 i * i <= n呢?这是因为 12 = 2 * 6,有了2就不需要另一部分了。
最后如有遗漏的情况也加上。
相关文章:
算法学习——GCD与欧拉函数
欧几里得GCD: GCD算法是使用辗转相除法求最大公因数的算法,简单而言就是gcd(a,b) gcd(b,a mod b) 递归写法: int Gcd(int a, int b) {if(b 0)return a;return Gcd(b, a % b); } 迭代写法: int Gcd(int a, int b) {while(b …...
40. 组合总和 II(力扣LeetCode)
文章目录 40. 组合总和 II题目描述回溯算法 40. 组合总和 II 题目描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意ÿ…...
Ubuntu上Jenkins自动化部署Gitee上SpringBoot项目
文章目录 安装安装JDK安装Maven安装GitNodeJS安装(可选)安装Jenkins 配置Jenkins为Jenkins更换插件源设置jenkins时区安装插件全局工具配置添加Gitee凭证Gitee项目配置 部署后端1.新建任务2.配置源码管理3.构建触发器4.到Gitee中添加WebHook5.构建环境6.…...
延迟任务基于DeyalQueue
一,延迟任务应用场景? 一般用于处理订单,将redis中的数据延迟存入数据库,实现异步存储减少DB的压力 二, 延迟任务的实现方案有很多 DelayQueue Redisson MQ 时间轮 原理 JDK自带延迟队列,基于阻塞队列…...
Linux 查询端口被占用命令
Linux 查询端口被占用命令 1、lsof -i:端口号 用于查看某一端口的占用情况,比如查看8000端口使用情况,lsof -i:8000 lsof -i:8080:查看8080端口占用 lsof abc.txt:显示开启文件abc.txt的进程 lsof -c abc:显示abc进…...
【c++】string类---标准库中的string类
1. 为什么要学习string类 1.1 C语言中的字符串 C语言中,字符串是以\0结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列 库函数,但是这些库函数与字符串是分离开的,不太符合OOP的思想,而且…...
GO语言学习笔记(与Java的比较学习)(五)
Map 概念 map 是引用类型,可以使用如下声明: var map1 map[keytype]valuetype var map1 map[string]int 在声明的时候不需要知道 map 的长度,map 是可以动态增长的。 未初始化的 map 的值是 nil(即零值为nil)&…...
Sora:探索大型视觉模型的前世今生、技术内核及未来趋势
Sora,一款由OpenAI在2024年2月推出的创新性文生视频的生成式AI模型,能够依据文字说明,创作出既真实又富有想象力的场景视频,展现了其在模拟现实世界方面的巨大潜能。本文基于公开技术文档和逆向工程分析,全面审视了Sor…...
基于springboot实现图书馆管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现图书馆管理系统演示 摘要 电脑的出现是一个时代的进步,不仅仅帮助人们解决了一些数学上的难题,如今电脑的出现,更加方便了人们在工作和生活中对于一些事物的处理。应用的越来越广泛,通过互联网我们可以更方便地…...
MATLAB环境下基于高斯滤波器-广义拉普拉斯算子的细胞核自动检测
作为病理图像分析的基础,细胞核检测可为细胞形态、纹理等多种相关分析提供支持,对于临床诊断具有重要意义。但是细胞核的人工识别过程十分费时费力,并且不同医生之间存在主观标注差异。因此,利用计算机技术进行自动检测能够更为客…...
【探索AI】十一 深度学习之第1周:深度学习概述与基础
深度学习概述与基础 深度学习的发展历史与现状神经网络的基本原理前向传播与反向传播算法常见的激活函数与优化算法深度学习框架(如TensorFlow或PyTorch)进行基础操作 深度学习的发展历史与现状 深度学习的发展历史可以追溯到上世纪40年代,当…...
【简说八股】Spring事务失效可能是哪些原因?
Spring事务介绍 Spring事务是指在Spring框架中对数据库操作进行管理的一种机制,它确保一组数据库操作要么完全执行成功(提交),要么完全不执行(回滚),从而保持数据一致性和完整性。 Spring框架…...
【语音识别】- CTC损失计算的原理
文章目录 1.符号定义与目标函数2.前向计算 α s ( t ) \alpha_s(t) α...
MySQL字符集和比较规则
MySQL字符集和比较规则 字符集和比较规则简介 字符集: 描述字符与二进制数据的映射关系 比较规则:比较指定字符集中的字符的规则 字符集 我们知道,计算机无法直接存储字符串,实际存储的都是二进制数据。字符集是有限的ÿ…...
备忘录模式(Memento Pattern)
定义 备忘录模式(Memento Pattern)是一种行为设计模式,它允许在不破坏封装性的前提下捕获一个对象的内部状态,并在以后将对象恢复到该状态。备忘录模式通常用于实现撤销操作(Undo)或历史记录(H…...
LeetCode 刷题 [C++] 第121题.买卖股票的最佳时机
题目描述 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的…...
ORACLE 基础
一.ORACLE简介 1.1什么是oracle ORACLE 数据库系统是美国 ORACLE 公司(甲骨文)提供的以分布式数据库为核心的一组软件产品,是目前最流行的客户/服务器(CLIENT/SERVER)或 B/S 体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。…...
Adobe illustrator CEP插件调试
1.创建插件CEP面板,可以参考:http://blog.nullice.com/%E6%8A%80%E6%9C%AF/CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B/%E6%8A%80%E6%9C%AF-CEP-%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8B-Adobe-CEP-%E6%89%A9%E5%B1%95%E5%BC%80%E5%8F%91%E6%95%99%E7%A8%8…...
学会玩游戏,智能究竟从何而来?
最近在读梅拉妮米歇尔《AI 3.0》第三部分第九章,谈到学会玩游戏,智能究竟从何而来? 作者: [美] 梅拉妮米歇尔 出版社: 四川科学技术出版社湛庐 原作名: Artificial Intelligence: A Guide for Thinking Humans 译者: 王飞跃 / 李玉珂 / 王晓…...
Unity 常用操作
2D素材网站 https://craftpix.net/ https://itch.io/game-assets/tag-2d/tag-backgrounds 3D素材资源网址 https://www.mixamo.com/#/ 场景常用操作: 快捷键:QWER Q:Q键或鼠标中键,可以拉动场景。 W:选中物体后&…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
