蓝桥杯AcWing学习笔记 8-2数论的学习(下)

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

数论(下)

蓝桥杯省赛中考的数论不是很多,这里讲几个蓝桥杯常考的知识点。

约数个数定理

我们如何去求一个数的约数个数呢?

N N N分解质因数的结果: N = P 1 α 1 × P 2 α 2 × . . . × P k α k N=P_{1}^{α_{1}}×P_{2}^{α_{2}}×...×P_{k}^{α_{k}} N=P1α1×P2α2×...×Pkαk

约数个数是: ( α 1 + 1 ) ( α 2 + 1 ) . . . ( α k + 1 ) (α_{1}+1)(α_{2}+1)...(α_{k}+1) (α1+1)(α2+1)...(αk+1)

假设 N N N的一个约数 d = P 1 β 1 × P 2 β 2 × . . . × P k β k ( 0 ≤ β i ≤ α i ) d=P_{1}^{β_{1}}×P_{2}^{β_{2}}×...×P_{k}^{β_{k}}(0 \leq β_{i}\leq α_{i}) d=P1β1×P2β2×...×Pkβk(0βiαi),每一个约数都可以表示为这样的形式,这种约数的个数也就等于 k k k 元组的个数: ( β 1 , β 2 . . . β k ) (β_{1},β_{2}...β_{k}) (β1,β2...βk),这 k k k 元组有多少种选法: ( α 1 + 1 ) ⋅ ( α 2 + 1 ) ⋅ ( α k + 1 ) (α_{1}+1)·(α_{2}+1)·(α_{k}+1) (α1+1)(α2+1)(αk+1)

约数和定理

公式: ( 1 + P 1 + P 1 2 + . . + P 1 α 1 ) ( 1 + P 2 + P 2 2 + . . + P 2 α 2 ) . . . ( 1 + P k + P k 2 + . . + P k α k ) (1+P_{1}+P_{1}^2+..+P_{1}^{α_{1}})(1+P_{2}+P_{2}^2+..+P_{2}^{α_{2}})...(1+P_{k}+P_{k}^2+..+P_{k}^{α_{k}}) (1+P1+P12+..+P1α1)(1+P2+P22+..+P2α2)...(1+Pk+Pk2+..+Pkαk)

这个公式展开了就是上面定理的约数 d = P 1 β 1 × P 2 β 2 × . . . × P k β k ( 0 ≤ β i ≤ α i ) d=P_{1}^{β_{1}}×P_{2}^{β_{2}}×...×P_{k}^{β_{k}}(0 \leq β_{i}\leq α_{i}) d=P1β1×P2β2×...×Pkβk(0βiαi) 之和。

image-20220306144504746

例题

AcWing 1296. 聪明的燕姿

约数个数定理

约数和定理

给我们一个 S S S,问我们有多少个正整数满足它的所有正约数之和等于 S S S

S S S 满足约数和定理: S = ( 1 + P 1 + P 1 2 + . . + P 1 α 1 ) ( 1 + P 2 + P 2 2 + . . + P 2 α 2 ) . . . ( 1 + P k + P k 2 + . . + P k α k ) S=(1+P_{1}+P_{1}^2+..+P_{1}^{α_{1}})(1+P_{2}+P_{2}^2+..+P_{2}^{α_{2}})...(1+P_{k}+P_{k}^2+..+P_{k}^{α_{k}}) S=(1+P1+P12+..+P1α1)(1+P2+P22+..+P2α2)...(1+Pk+Pk2+..+Pkαk)

因为方案数非常少,我们可以用暴搜dfs求解。

这题太难理解啦,之后的题也没有做了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/239737.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

kubeSphere DevOps部署vue项目

devops部署vue项目 🌔环境说明🌏创建DevOps工程🌏填写流水线信息🌏创建流水线 🌔部署应用所需脚本JenkinsfileDockerfile 🌔脚本一些参数如何设置说明🌏deploy.yaml中的:imagePullSecrets:name属…

部署 LVS-DR 群集

本章内容: -了解LVS-DR群集的工作原理 -会构建LVS-DR负载均衡群集 2.1 LVS-DR 集群 LVS-DR ( Linux Virtual Server Director Server )工作模式,是生产环境中最常用的一 种工作模式。 2.1.1 . LVS-DR 工作原理 …

JVM运行时数据区(下篇)

紧接上篇:JVM运行时数据区(上篇)-CSDN博客 堆 一般Java程序中堆内存是空间最大的一块内存区域。创建出来的对象都存在于堆上。 栈上的局部变量表中,可以存放堆上对象的引用。静态变量也可以存放堆对象的引用,通过静态…

记录Qt和opencv 新环境配置过程

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、Qt是什么?二、Qt的版本三、安装步骤1.下载Qt2.双击安装包.exe开始安装3. 需要登陆才能继续安装,没有的就用邮箱注册账号4.注意安装路…

linux创建文件

创建文件夹: mkdir folder_name其中,folder_name是想要创建的文件夹的名称。 例如,如果想在当前目录下创建一个名为 "my_folder" 的文件夹,可以运行以下命令: mkdir my_folder如果想在特定路径下创建文件…

element-ui el-table表格勾选框条件禁用,及全勾选按钮禁用, 记录

项目场景: 表格的部分内容是可以被勾选的,部分内容是不可以被勾选的 使用的是 “element-plus”: “^2.2.22”, 以上应该都是兼容的 问题描述 要求el-table表格中,部分内容不可以被勾选,全选框在没有可选内容时,是禁…

RK3566RK3568安卓11隐藏状态栏带接口

文章目录 前言一、创建全局变量二、设置应用添加隐藏导航栏按钮三、添加按钮功能四、动态隐藏还有显示功能五、创建系统导航栏广播接口总结 前言 关于Android系统的状态栏,不同的客户有不同的需求: 有些客户需要永久隐藏状态栏,有些客户需要在设置显示中…

Flask框架小程序后端分离开发学习笔记《1》网络知识

Flask框架小程序后端分离开发学习笔记《1》网络知识 Flask是使用python的后端,由于小程序需要后端开发,遂学习一下后端开发。 一、网址组成介绍 协议:http,https (https是加密的http)主机:g.cn zhihu.com之类的网址…

通义灵码 - 免费的阿里云 VS code Jetbrains AI 编码辅助工具

系列文章目录 前言 通义灵码,是阿里云出品的一款基于通义大模型的智能编码辅助工具,提供行级/函数级实时续写、自然语言生成代码、单元测试生成、代码注释生成、代码解释、研发智能问答、异常报错排查等能力,并针对阿里云 SDK/OpenAPI 的使用…

【Java 设计模式】创建型之建造者模式

文章目录 1. 定义2. 应用场景3. 代码实现4. 应用示例结语 在软件开发中,建造者模式是一种创建型设计模式,它将一个复杂对象的构建与其表示分离,使得同样的构建过程可以创建不同的表示。建造者模式通常包括一个指导者(Director&…

如何在 SwiftUI 中实现音频图表

文章目录 前言DataPoint 结构体BarChartView 结构体ContentView 结构体实现协议实现线图总结 前言 在可访问性方面,图表是复杂的事物之一。iOS 15 引入了一项名为“音频图表”的新功能。 下面我们将学习如何通过使用 accessibilityChartDescriptor 视图修饰符为任…

远程开发之vscode端口转发

远程开发之vscode端口转发 涉及的软件forwarded port 通过端口转发,实现在本地电脑上访问远程服务器上的内网的服务。 涉及的软件 vscode、ssh forwarded port 在ports界面中的port字段,填需要转发的IP:PORT,即可转发远程服务器中的内网端…

十、Three场景实现多个物体的合并

Three场景实现多个物体的合并 目的 产品需求是让物体的光柱墙包含一个多边形的区域,二而我的多边形只能使用原型,方向,多边形。那么再研究的时候就需要将这些多边形合并成为一个形状,那么就行实现了。 原先的图形 如上图,是两个mesh组成的。首先寻找mesh合并的方法。 第…

java日志框架总结

一、日志框架简单分类介绍 java常用的日志框架、可以分为两组: 1、JCL、JUL、Log4j; 2、SLF4J、Log4j2、Logback; 其中第一组是比较早期的日志实现框架,JCL并不是具体的日志实现框架,JCL其实是定义了一…

网络安全笔记-SQL注入

文章目录 前言一、数据库1、Information_schema2、相关函数 二、SQL注入分类1、联合查询注入(UNION query SQL injection)语法 2、报错注入(Error-based SQL injection)报错注入分类报错函数报错注入原理 3、盲注布尔型盲注&#…

RK3568笔记八: Display子系统

modetest 是由 libdrm 提供的测试程序,可以查询显示设备的特性,进行基本的显示测试,以及设置显示的模式。 我们可以借助该工具来学习 Linux DRM 应用编程,另外为了深入分析 Rockchip DRM driver,有必要先了解一下这个…

1.环境部署

1.虚拟机安装redhat8系统 这个其实很简单,但是有一点小细节需要注意。 因为我的电脑是 16核心的,所以选择内核16,可以最大发挥虚拟机的性能 磁盘选择SATA,便于后期学习 将一些没用的设备移除 选择安装redhat 8 时间选择上海 选择…

逻辑回归(解决分类问题)

定义:逻辑回归是一种用于解决分类问题的统计学习方法。它通过对数据进行建模,预测一个事件发生的概率。逻辑回归通常用于二元分类问题,即将数据分为两个类别。它基于线性回归模型,但使用了逻辑函数(也称为S形函数&…

用Python“自动连发消息”

自动连发消息,基本上C和Python的思路都是不停的模拟“击键”操作,还有一种VB的脚本写法,反成每种语言都能写,更厉害的可以用java做出个GUI界面,先上代码。 一 代码 import pyautogui # 鼠标 import p…

C++I/O流——(2)预定义格式的输入/输出(第二节)

归纳编程学习的感悟, 记录奋斗路上的点滴, 希望能帮到一样刻苦的你! 如有不足欢迎指正! 共同学习交流! 🌎欢迎各位→点赞 👍 收藏⭐ 留言​📝 含泪播种的人一定能含笑收获&#xff…