欧拉计划 Project Euler 21题解
欧拉计划21
- Project Euler Problem21
- 题干
- 亲和数
- 约数和的计算
- 定义
- 对于任何素数 \( p \):
- 考虑 p a p^a pa:
- 示例
- 可乘性
- 回到示例
Project Euler Problem21
题干
亲和数
记 d ( n ) d(n) d(n) 为 n 的所有真约数(小于 n 且整除 n 的正整数)之和。
如果 d(a) = b , d(b) = a ,而且 a != b ,那么 a 和 b 构成一个亲和数对, a 和 b 都被称为亲和数。
例如:
- 220 的真因数包括 1、2、4、5、10、11、20、22、44、55 和 110,因此 d ( 220 ) = 284 d(220) = 284 d(220)=284;
- 而 284 的真因数包括 1、2、4、71 和 142,因此 d ( 284 ) = 220 d(284) = 220 d(284)=220。
求所有小于 10000 的亲和数之和。
初步的思路肯定是暴力枚举 以下是暴力的代码
// 31626#include <bits/stdc++.h>using namespace std;using ll = long long;
// 求真因数之和
int get(int n) {int sum = 1;for (int i = 2; i <= sqrt(n); ++i) {if (n % i == 0) {sum += i;if (i != n / i) {sum += n / i;}}}return sum;
}void solve() {const int LIMIT = 10000;vector<int> divs(LIMIT, 0);for (int i = 1; i < LIMIT; ++i) {divs[i] = get(i);}int ans = 0;for (int a = 1; a < LIMIT; ++a) {int b = divs[a];if (b < LIMIT && b != a && divs[b] == a) {ans += a;}}cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}
约数和的计算
假设你想计算数字 72 的所有约数之和。列出所有约数并求和并不复杂:
1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 + 72 = 195。
然而,对于像 145600 这样的大数字,这种方法会变得既繁琐又困难。幸运的是,这里有一种简单优雅的方法。
定义
设 $ \sigma(n) $ 表示自然数 n的所有约数之和。
对于任何素数 ( p ):
σ ( p ) = p + 1 \sigma(p) = p + 1 σ(p)=p+1
因为它的唯一约数是 1 和 p 。
考虑 p a p^a pa:
σ ( p a ) = 1 + p + p 2 + ⋯ + p a (1) \sigma(p^a) = 1 + p + p^2 + \dots + p^a \tag{1} σ(pa)=1+p+p2+⋯+pa(1)
将其乘以 p :
p σ ( p a ) = p + p 2 + p 3 + ⋯ + p a + 1 (2) p \sigma(p^a) = p + p^2 + p^3 + \dots + p^{a+1} \tag{2} pσ(pa)=p+p2+p3+⋯+pa+1(2)
从 (2) 中减去 (1):
p σ ( p a ) − σ ( p a ) = ( p − 1 ) σ ( p a ) = p a + 1 − 1 p \sigma(p^a) - \sigma(p^a) = (p - 1) \sigma(p^a) = p^{a+1} - 1 pσ(pa)−σ(pa)=(p−1)σ(pa)=pa+1−1
因此:
σ ( p a ) = p a + 1 − 1 p − 1 \sigma(p^a) = \frac{p^{a+1} - 1}{p - 1} σ(pa)=p−1pa+1−1
当然用等比数列求和公式也可以直接得到该结果
示例
例如:
σ ( 3 4 ) = 3 5 − 1 3 − 1 = 243 − 1 2 = 121 \sigma(3^4) = \frac{3^5 - 1}{3 - 1} = \frac{243 - 1}{2} = 121 σ(34)=3−135−1=2243−1=121
验证一下:
1 + 3 + 9 + 27 + 81 = 121 1 + 3 + 9 + 27 + 81 = 121 1+3+9+27+81=121
可乘性
虽然这里没有提供证明,但函数 $ \sigma(n) $ 的一个重要特性是其 可乘性,即:
σ ( a × b × … ) = σ ( a ) × σ ( b ) × … \sigma(a \times b \times \dots) = \sigma(a) \times \sigma(b) \times \dots σ(a×b×…)=σ(a)×σ(b)×…
其中 a, b, …, 是互质的。
回到示例
利用这一性质,我们计算:
σ ( 72 ) = σ ( 2 3 × 3 2 ) \sigma(72) = \sigma(2^3 \times 3^2) σ(72)=σ(23×32)
由于 ( 2^3 ) 和 ( 3^2 ) 是互质的,我们分别计算:
σ ( 2 3 ) = 2 4 − 1 2 − 1 = 15 \sigma(2^3) = \frac{2^4 - 1}{2 - 1} = 15 σ(23)=2−124−1=15
σ ( 3 2 ) = 3 3 − 1 3 − 1 = 13 \sigma(3^2) = \frac{3^3 - 1}{3 - 1} = 13 σ(32)=3−133−1=13
因此: σ ( 72 ) = 15 ∗ 13 = 195 \sigma(72) = 15 * 13 = 195 σ(72)=15∗13=195
利用上诉的性质我们可以更好的优化该题
c++代码如下
// 31626#include <bits/stdc++.h>using namespace std;using ll = long long;int get(int n) {int originalN = n;int sum = 1;for (int p = 2; p * p <= n; ++p) {if (n % p == 0) {int powerSum = 1; // p^0 + p^1 + ... + p^kint curPower = 1;while (n % p == 0) {n /= p;curPower *= p;powerSum += curPower;}sum *= powerSum;}}// 如果剩下一个大于sqrt(n)的素因子if (n > 1) {sum *= (n + 1);}return sum - originalN;
}void solve() {const int LIMIT = 10000;vector<int> divs(LIMIT, 0);for (int i = 1; i < LIMIT; ++i) {divs[i] = get(i);}int ans = 0;for (int a = 1; a < LIMIT; ++a) {int b = divs[a];if (b < LIMIT && b != a && divs[b] == a) {ans += a;}}cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}
相关文章:
欧拉计划 Project Euler 21题解
欧拉计划21 Project Euler Problem21题干亲和数约数和的计算定义对于任何素数 \( p \):考虑 p a p^a pa:示例可乘性回到示例 Project Euler Problem21 题干 亲和数 记 d ( n ) d(n) d(n) 为 n 的所有真约数(小于 n 且整除 n 的正整数)之和。 如果 d(a) b , d(b) a &…...
python中的Counter函数
在 Python 中,Counter 是 collections 模块中的一个类,用于统计可迭代对象中元素的出现次数,并以字典的形式返回,键为元素,值为对应的计数。它非常适合处理频率统计问题。 用之前必须先导入 from collections import…...
WPF+MVVM案例实战与特效(三十七)- 实现带有水印和圆角的自定义 TextBox 控件
文章目录 1、概述2、案例实现1、基本功能2、代码实现3、控件应用4、案例效果5、源代码下载4、总结1、概述 在开发用户界面时,TextBox 是最常见的输入控件之一。为了提升用户体验,我们经常需要为 TextBox 添加一些额外的功能,例如显示提示文本(水印)和设置圆角边框。本文将…...
SQLServer到MySQL的数据高效迁移方案分享
SQL Server数据集成到MySQL的技术案例分享 在企业级数据管理中,跨平台的数据集成是一个常见且关键的任务。本次我们将探讨如何通过轻易云数据集成平台,将巨益OMS系统中的退款单明细表从SQL Server高效、安全地迁移到MySQL数据库中。具体方案名称为“7--…...
docker快速实现ELK的安装和使用
目录 一、ELK功能原理 二、项目功能展示 三、日志查询展示 四、ELK安装步骤 1、创建elasticsearch、kibana、filebeat相关data、log、conf目录 2、进入/usr/local/elk目录,并创建一个docker网络 3、启动 elasticsearch容器 4、运行kibana容器 5、启动f…...
hbase读写操作后hdfs内存占用太大的问题
hbase读写操作后hdfs内存占用太大的问题 查看内存信息hbase读写操作 查看内存信息 查看本地磁盘的内存信息 df -h查看hdfs上根目录下各个文件的内存大小 hdfs dfs -du -h /查看hdfs上/hbase目录下各个文件的内存大小 hdfs dfs -du -h /hbase查看hdfs上/hbase/oldWALs目录下…...
解决vue2中更新列表数据,页面dom没有重新渲染的问题
在 Vue 2 中,直接修改数组的某个项可能不会触发视图的更新。这是因为 Vue 不能检测到数组的索引变化或对象属性的直接赋值。为了确保 Vue 能够正确地响应数据变化,你可以使用以下几种方法: 1. 使用 Vue.set() 使用 Vue.set() 方法可以确保 …...
Go语言错误分类
错误的分类 在 Go 语言中,错误是通过实现 error 接口的类型表示的,但不同场景下的错误可以按性质和用途进行分类。以下是 Go 语言错误的常见分类,以及每类错误的解释和示例: 标准错误类型 标准库中定义了许多常见的错误类型&…...
使用 Ansys Fluent 对气体泄漏检测进行建模
了解使用 Ansys Fluent 仿真气体泄漏和确保安全的前沿技术。 挑战 气体泄漏对人类安全和环境构成重大风险。及早检测气体泄漏可以防止潜在的灾难,包括爆炸、火灾和有毒物质暴露。有效的气体泄漏检测系统对于石油和天然气、化学加工和住宅基础设施等行业至关重要。…...
Pytest-Bdd-Playwright 系列教程(16):标准化JSON报告Gherkin格式命令行报告
Pytest-Bdd-Playwright 系列教程(16):标准化JSON报告&Gherkin格式命令行报告 前言一、创建Feature文件二、创建步骤定义文件三、生成Cucumber格式的JSON报告四、使用Gherkin格式的命令行报告五、将BDD报告集成到Jenkins中总结 前言 在自动…...
lc46全排列——回溯
46. 全排列 - 力扣(LeetCode) 法1:暴力枚举 总共n!种全排列,一一列举出来放入list就行,关键是怎么去枚举呢?那就每次随机取一个,然后删去这个,再从剩下的数组中继续去随机选一个&a…...
软考:工作后再考的性价比分析
引言 在当今的就业市场中,软考(软件设计师、系统分析师等资格考试)是否值得在校学生花费时间和精力去准备?本文将从多个角度深入分析软考在不同阶段的性价比,帮助大家做出明智的选择。 一、软考的价值与局限性 1.1 …...
如何设置 Data Guard 的报警机制?
概述 设置 Data Guard 的报警机制是确保高可用性和及时响应故障的关键步骤。以下是一些常见的方法来配置 Data Guard 的报警机制,包括使用 Oracle Enterprise Manager (OEM)、Data Guard Broker 以及自定义脚本和外部监控工具。 1. 使用 Oracle Enterprise Manage…...
Elastic 8.17:Elasticsearch logsdb 索引模式、Elastic Rerank 等
作者:来自 Elastic Brian Bergholm 今天,我们很高兴地宣布 Elastic 8.17 正式发布! 紧随一个月前发布的 Elastic 8.16 之后,我们将 Elastic 8.17 的重点放在快速跟踪关键功能上,这些功能将带来存储节省和搜索性能优势…...
Please activate LaTeX Workshop sidebar item to render the thumbnail of a PDF
Latex代码中使用pdf图片,无法预览,提示: Please activate LaTeX Workshop sidebar item to render the thumbnail of a PDF 解决办法: 点击左边这个刷新下即可...
HiveQL命令(一)- 数据库操作
文章目录 前言一、数据库操作1. 创建数据库1.1 语法及解释1.2 创建数据库示例 2. 查看数据库2.1 查看所有数据库2.2 查看数据库信息2.2.1 语法及解释2.2.2 查看数据库信息示例 3. 切换数据库3.1 语法3.2 示例 4. 修改数据库4.1 语法4.2 示例 5. 删除数据库5.1 语法及解释5.2 示…...
【esp32s3】esp-dl模型部署demo
一个单片机部署手写数字识别的demo 源码: # 别跑,给我star git clone https://gitee.com/Shine_Zhang/esp32s3_dl_helloworld.git功能: 网页绘制28x28手写数字,串口输入设备,串口打印输出10个数字的概率值࿰…...
Zemax 中的 LED 阵列模型
LED 阵列的光学特性 LED 阵列由多个发光二极管 (LED) 组成,这些二极管以特定模式或配置排列,以实现均匀照明、更高强度或特定照明特性。这些阵列广泛用于显示器、照明系统、光通信和传感等应用。 LED 阵列的光学特性对于了解它如…...
123213124
📢博客主页:https://blog.csdn.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由 JohnKi 原创,首发于 CSDN🙉 📢未来很长&#…...
游戏引擎学习第42天
仓库: https://gitee.com/mrxiao_com/2d_game 简介 目前我们正在研究的内容是如何构建一个基本的游戏引擎。我们将深入了解游戏开发的每一个环节,从最基础的技术实现到高级的游戏编程。 角色移动代码 我们主要讨论的是角色的移动代码。我一直希望能够使用一些基…...
elasticsearch设置密码访问
1 用户认证介绍 默认ES是没有设置用户认证访问的,所以每次访问时,直接调相关API就能查询和写入数据。现在做一个认证,只有通过认证的用户才能访问和操作ES。 2 开启加密设置 1.生成证书文件 /usr/share/elasticsearch/bin/elasticsearch-…...
阿里云-通义灵码:测试与实例展示
目录 一.引子 二.例子 三.优点 四.其他优点 五.总结 一.引子 在软件开发的广袤天地中,阿里云通义灵码宛如一座蕴藏无尽智慧的宝库,等待着开发者们去深入挖掘和探索。当我们跨越了入门的门槛,真正开始使用通义灵码进行代码生成和开发工作…...
开发者指南--RecyclerView显示数据列表和网格
一、RecyclerView的优势 RecyclerView 的最大优势在于,它对大型列表来说非常高效: 默认情况下,RecyclerView 仅会处理或绘制当前显示在屏幕上的项。例如,如果您的列表包含一千个元素,但只有 10 个元素可见࿰…...
Ajax--实现检测用户名是否存在功能
目录 (一)什么是Ajax (二)同步交互与异步交互 (三)AJAX常见应用情景 (四)AJAX的优缺点 (五)使用jQuery实现AJAX 1.使用JQuery中的ajax方法实现步骤…...
操作系统(5)进程
一、定义与特点 定义:进程是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。 特点: 动态性:进程是动态创建的,有它自身的生命周期,…...
力扣9. 回文数
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数 是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 例如,121 是回文,而…...
1_linux系统网络性能如何优化——几种开源网络协议栈比较
之前合集《计算机网络从入门到放弃》第一阶段算是已经完成了。都是理论,没有实操,让“程序猿”很难受,操作性不如 Modbus发送的报文何时等到应答和 tcp通信测试报告单1——connect和send。开始是想看linux内核网络协议栈的源码,然…...
C#—BitArray点阵列
C#—BitArray点阵列 在 C# 中,BitArray 类用来管理一个紧凑型的位值数组,数组中的值均为布尔类型,其中 true(1)表示此位为开启,false(0)表示此位为关闭。 当需要存储位(…...
特工找密码(蓝桥杯)
本来这题想用枚举暴力解的,但是运行总是超时,数值范围太大了~,所以该题不能用枚举进行暴力。 转换成二进制,我们判断一下其规律 注意:按位与是都为1时其值才为1,所以当x和y按位与的结果为2时,其…...
微信小程序--创建一个日历组件
微信小程序–创建一个日历组件 可以创建一个日历组件,来展示当前月份的日期,并支持切换月份的功能。 一、目录结构 /pages/calendarcalendar.wxmlcalendar.scsscalendar.jscalendar.json二、calendar.wxml <view class"calendar"><…...
A6919 基于java+SSM+mysql的区域物流管理系统设计与实现
的区域物流管理系统的设计与实现 1.摘要2.开发目的和意义3.系统功能设计4.系统界面截图5.源码获取 1.摘要 摘 要 随着当前我国市场经济和计算机互联网技术迅速发展,各行各业的销售和管理都在逐步转向着第三方物流服务,包括中通快递,申通&…...
Python大数据可视化:基于python的电影天堂数据可视化_django+hive
开发语言:Python框架:djangoPython版本:python3.7.7数据库:mysql 5.7数据库工具:Navicat11开发软件:PyCharm 系统展示 管理员登录 管理员功能界面 电影数据 看板展示 我的信息 摘要 电影天堂数据可视化是…...
美畅物联丨JS播放器录像功能:从技术到应用的全面解析
畅联云平台的JS播放器是一款功能十分强大的视频汇聚平台播放工具,它已经具备众多实用功能,像实时播放、历史录像回放、云台控制、倍速播放、录像记录、音频播放、画面放大、全屏展示、截图捕捉等等。这些功能构建起了一个高效、灵活且用户友好的播放环境…...
前端国际化实战:从需求到落地的完整实践
"我们要开拓东南亚市场了!"产品经理小王兴奋地告诉我这个消息。作为技术负责人,我立刻意识到这意味着我们需要对整个系统进行国际化改造。说实话,虽然之前也做过一些多语言的项目,但面对一个正在运行的大型系统,国际化改造的挑战还是不小。 回想起上周的…...
MySQL 内置函数
字符串函数 concat(str1, str2, ...) 描述: 这个函数用于连接两个或多个字符串,返回一个新字符串。语法: concat(str1, str2, ...)注意点: 如果任意一个参数是null,则结果为null。可以连接任意数量的字符串。示例: select concat(first name: , first_…...
【Spring】日志类Logger的使用
在Spring框架中,日志记录是一个重要的组成部分,通常使用不同的日志框架来处理应用程序的日志。Spring 本身并直接提供一个名为Logger 的类,而是通过抽象的日志 API 让开发者能够选择和使用不同的日志实现(如 Log4j、Logback、SLF4…...
动态高优先权优先进程调度
一、实验目的 目的:了解并掌握动态高优先权优先调度算法的理论,掌握动态优先权的设置方式。 任务:模拟实现动态高优先权优先的调度(若数值越大优先权越高,每运行一个时间单位优先权-n,若数值越小优先权越高…...
【Linux SH脚本】LinuxCheck 应急检查信息脚本
LinuxCheck 1.下载地址 【Linux SH脚本】LinuxCheck 应急检查信息脚本 2.简介 LinuxCheck 是一个开源的自动化检查脚本,旨在快速检测 Linux 系统的安全配置和潜在问题。它支持多种发行版,能够扫描并生成详细的报告,涵盖用户管理、权限配置…...
Vue - route路由(router-link、useRoute、useRouter)
为了避免反复在 app.vue 中去修改引入的路径,当用了新的页面,想切换回老页面的时候,都需要去手动改变路径,那么有没有一种可能,可以在一个地方,把这些组件配置好,然后通过不同的路径,…...
【HarmonyOS】鸿蒙应用实现手机摇一摇功能
【HarmonyOS】鸿蒙应用实现手机摇一摇功能 一、前言 手机摇一摇功能,是通过获取手机设备,加速度传感器接口,获取其中的数值,进行逻辑判断实现的功能。 在鸿蒙中手机设备传感器ohos.sensor (传感器)的系统API监听有以下…...
渗透测试工具 -- SQLmap安装教程及使用
随着网络安全问题日益严峻,渗透测试成为了保护信息安全的重要手段。而在渗透测试的众多工具中,SQLmap凭借其强大的自动化SQL注入检测和利用能力,成为了网络安全专家必备的利器。那么,你知道如何高效地使用SQLmap进行漏洞扫描吗&am…...
vue 前端使用fetch实现下载文件跨域
首先配置vite.config.js export default defineConfig({plugins: [vue(),],resolve: {alias: {: /src, // 根据你的项目结构进行设置},},server: {proxy: {/image-proxy: {target: https://你得代理服务器,changeOrigin: true,rewrite: path > path.replace(/^/image-proxy…...
AI与大数据的深度结合:驱动决策的革命性力量
引言:数字时代的决策挑战 在这个信息爆炸的数字时代,数据早已渗透到我们生活的方方面面。全球每天产生的数据量呈指数级增长,无论是用户的消费行为、设备的运行状态,还是社会热点的实时动态,这些信息的规模和复杂性前所…...
搭建C#开发环境
本文记录C#开发环境的搭建过程。 一、Windows系统 二、Ubuntu 运行以下命令安装.NET SDK, sudo add-apt-repository ppa:dotnet/backports sudo apt-get install -y dotnet-sdk-9.0网络资料 Install .NET on Windowshttps://learn.microsoft.com/en-us/dotnet/co…...
Gitlab分支合并及在本地解决冲突
文章目录 问题及解决参考 问题及解决 Gitlab分支合并时碰到了合并冲突的问题,进行了本地解决冲突的操作,并成功进行了合并。 在服务器端的冲突解决比较简单,在此不赘述,这里主要记录下在本地解决冲突的操作。 Gitlab冲突的根本…...
解决 “TypeError: ‘tuple‘ object cannot be interpreted as an integer“ 错误提示
错误背景 这个错误通常出现在期望一个整数时,却传入了一个元组(tuple)。Python 无法将元组解释为整数,因此会抛出 TypeError。 错误示例 python 复制代码 for i in (1, 2, 3): print(range(i)) 运行时会抛出如下错误:…...
OSPF协议
OSPF介绍 OSPF(Open Shortest Path First,开放最短路径优先)是一种用于互联网协议网络的链路状态路由协议。它属于内部网关协议(IGP),主要用于单一自治系统(AS)内部的路由选择。在A…...
前端编辑器JSON HTML等,vue2-ace-editor,vue3-ace-editor
与框架无关 vue2-ace-editor有问题,ace拿不到(brace) 一些组件都是基于ace-builds或者brace包装的 不如直接用下面的,不如直接使用下面的 <template><div ref"editor" class"json-editor"><…...
threejs——无人机概念切割效果
主要技术采用着色器的切割渲染,和之前写的风车可视化的文章不同,这次的切割效果是在着色器的基础上实现的,并新增了很多可调节的变量,兄弟们,走曲儿~ 线上演示地址,点击体验 源码下载地址,点击下载 正文 从图中大概可以看出以下信息,一个由线组成的无人机模型,一个由…...
360极速浏览器不支持看PDF
360安全浏览器采用的是基于IE内核和Chrome内核的双核浏览器。360极速浏览器是源自Chromium开源项目的浏览器,不但完美融合了IE内核引擎,而且实现了双核引擎的无缝切换。因此在速度上,360极速浏览器的极速体验感更佳。 展示自己的时候要在有优…...