数据结构与算法-数学-基础数学算法（筛质数，最大公约数，最小公倍数，质因数算法，快速幂，乘法逆元，欧拉函数）
一：筛质数：
1-埃氏筛法
该算法核心是从 2 开始，把每个质数的倍数标记为合数，时间复杂度约为 O(nloglogn)。
#include <iostream>
#include <vector>u
sing namespace std;
const int N = 1000010;
bool st[N]; // 标记数组，true表示是合数，false表示是质数
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) {
for (int j = i + i; j <= n; j += i) {
st[j] = true;
}
}
}}
int main() {
int n;
cin >> n;
get_primes(n);
for (int i = 2; i <= n; i++) {
if (!st[i]) cout << i << ' ';
}
return 0;}
2-线性筛法：
在埃氏筛法的基础上进行进一步的优化，保证所有的合数都是被最小的质因子筛掉
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010;
int primes[N], cnt; // primes数组存储质数，cnt记录质数个数
bool st[N]; // 标记数组，true表示是合数，false表示是质数
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int n;
cin >> n;
get_primes(n);
for (int i = 0; i < cnt; i++) {
cout << primes[i] << ' ';
}
return 0;
}
二：最大公约数和最小公倍数
最小公约数：
是扩展欧几里得的基础版本，可以求出a和b的最小公约数
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
return 0;
}
最小公倍数：
int lcm(int a, int b) {
return a*b/gcd(a, b);
}
三：质因数：分解质因数，质因数的和，质因数个数
分解质因数：
一个很暴力的做法，最后得到n的所有质因数
#include <iostream>
using namespace std;
void divide(int x) {
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
cout << i << ' ' << s << endl;
}
}
if (x > 1) cout << x << ' ' << 1 << endl;
}
int main() {
int n;
cin >> n;
divide(n);
return 0;
}
约数的个数
若 N=p1^a1*p2^a2*⋯pk^ak，则 N 的约数个数为 (a1+1)(a2+1)⋯(ak+1)。
#include <iostream>
using namespace std;
int numofdividors(int x) {
int res=1;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
cout << i << ' ' << s << endl;
res=res*(s+1);
}
}
if (x > 1){
cout << x << ' ' << 1 << endl;
res*=2;
}
return res;
}
int main() {
int n;
cin >> n;
cout<<divide(n);
return 0;
}
约数的和
N=p1^a1*p2^a2⋯pk^ak则 N 的
约数和为 (p1^0+p1^1+⋯+p1^a1)(p2^0+p2^1+⋯+p2^a2)⋯(pk^0+pk^1++pk^ak)。
int main() {
int n;
cin >> n;
unordered_map<int, int> primes;
while (n--) {
int x;
cin >> x;
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
x /= i;
primes[i]++;
}
}
if (x > 1) primes[x]++;
}
LL res = 1;
for (auto p : primes) {
LL a = p.first, b = p.second;
LL t = 1;
while (b--) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
四：快速幂和乘法逆元
快速幂可以在logn级别的时间里确定n^b mod p
#include <iostream>
using namespace std;
typedef long long LL;
快速幂：
LL qmi(int a, int k, int p) {
LL res = 1;
while (k) {
if (k & 1) res = res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main() {
int a, k, p;
cin >> a >> k >> p;
cout << qmi(a, k, p) << endl;
return 0;
}
乘法逆元：
在mod p的环境下 a^-1 = a^ (p-2)
#include <iostream>
using namespace std;
typedef long long LL;
LL qmi(int a, int k, int p) {
LL res = 1;
while (k) {
if (k & 1) res = res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int main() {
int a, p;
cin >> a >> p;
if (a % p == 0) cout << "impossible" << endl;
else cout << qmi(a, p - 2, p) << endl;
return 0;
}
五：欧拉函数
欧拉函数 φ(n) 表示小于等于 n 且与 n 互质的正整数的个数。若 n=p1^a1*p2^a2*⋯pk^ak，
则 φ(n)=n(1−1/p1)(1−1/p2)⋯(1−1/pk)。
欧拉函数模版：
求出某一个数的欧拉函数值
#include <iostream>using namespace std;
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;}
int main() {
int n;
cin >> n;
cout << phi(n) << endl;
return 0;
}
线性筛法求出1~n的欧拉函数：
只有一点点的改变
#include <iostream>
#include <vector>
using namespace std;
const int N = 1000010;
int primes[N], cnt; // primes数组存储质数，cnt记录质数个数
bool st[N]; // 标记数组，true表示是合数，false表示是质数
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
phi[cnt-1]=i-1;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*（prime[j]-1）;
}
}
}
int main() {
int n;
cin >> n;
get_primes(n);
for (int i = 0; i < cnt; i++) {
cout << primes[i] << ' ';
}
return 0;
}
相关文章：
数据结构与算法-数学-基础数学算法（筛质数，最大公约数，最小公倍数，质因数算法，快速幂，乘法逆元，欧拉函数）
一：筛质数： 1-埃氏筛法 该算法核心是从 2 开始，把每个质数的倍数标记为合数，时间复杂度约为 O(nloglogn)。 #include <iostream> #include <vector>u sing namespace std; const int N 1000010; bool st[N]; …...
elasticSearch-搜索引擎
搜索引擎的优势 有了数据库分页查询，为什么还需要搜索引擎？ 搜索引擎速度上很快数据库分页查询，随着数据库数据量增大，页数靠后，会导致搜索速度变慢，但是搜索引擎不会搜索引擎支持分词查询，地…...
MQTT-Dashboard-数据集成
sink [sɪŋk] 下沉；沉没；沉降；...
uni-app项目运行在浏览器、微信开发者工具、mumu模拟器
一、安装HBuilder X 1、下载HBuilder X 官网网址：https://dcloud.io/hbuilderx.html 根据电脑系统下载对应的版本（我的电脑是Windows 10） 2.安装HBuilder X 直接将HBuilderX.4.61.2025040322-alpha.zip解压到自己想要存放的文件夹中 双击…...
从零开始微调Embedding模型：基于BERT的实战教程
文章目录 背景微调实战装包介绍 项目文件介绍微调硬件配置要求 debug 重要代码分析【选看】资源分享参考资料 背景 在理解与学会了Naive RAG的框架流程后，就很自然地关注到embedding模型，与问题相关的文本召回，也有很多论文在做这方面的创新…...
)
机器学习（神经网络基础篇）——个人理解篇5(梯度下降中遇到的问题)
在神经网络训练中，计算参数的梯度是关键步骤。numerical_gradient 方法旨在通过数值微分（中心差分法）计算损失函数对网络参数的梯度。然而，该方法的实现存在一个关键问题，导致梯度计算错误。 1、错误代码示例…...
)
带label的3D饼图（threejs)
3D饼图 使用three.js实现，选择threejs的原因：label需要实际的显示在具体的饼对应的模块上 “three”: “^0.127.0”, <template><div><div ref"chartContainer" class"chart-container"></div><div clas…...
ragflow开启https访问:使用自签证书还是有不安全警告,如何解决
背景:在ragflow里的使用了自签证书来启动ragflow,在浏览器里访问还是不安全警告,如何解决 在方案2中，证书不会在访问网站时自动下载，需要你手动获取并安装证书文件。以下是具体操作步骤： 详细步骤：手动获取并安装自签名证书 第一步：获取证书文件 找到证书文件 证书文件位…...
条件变量核心要素
条件变量内部实现原理 原子性解锁阻塞机制： // pthread_cond_wait内部伪代码大致如下： int pthread_cond_wait(cond_t *cond, mutex_t *mutex) {atomic {unlock(mutex); // 原子操作中先释放互斥锁block_thread(); // 立即将线程加入等待队列…...
C语言求鞍点
我们先在第一行中找出最大的值，然后在该列中找出最小值看这两个是否相等。 若是相等，那么这个数就是鞍点跳出循环 若是不想等，则继续在下一行寻找，若是一直到整体的循环都结束了还是没有，那么不存在鞍点。 运行结果:…...
XELA机器人多种“形态和玩法”的Uskin磁性阵列式三轴触觉传感器，你使用过了吗？
XELA Robotics为机器人行业提供创新的磁性触觉传感技术，uSkin触觉传感器是一种高密度的三轴触觉传感器，因其轻薄、表面柔软耐用和布线少的结构设计，可以轻松集成到机器人本体，灵巧手，机器人夹爪等部位，使机…...
转换效率高达 96%，12V转5V同步降压WD5030
特点1 宽输入电压范围：能在 7V 至 30V 的宽输入电压范围内工作，可适应多种不同电压等级的供电环境，无论是工业设备中的较高电压输入，还是便携式设备经过初步升压后的电压，都能良好适配，极大地拓展了应用的…...
请你回答一下单元测试、集成测试、系统测试、验收测试、回归测试这几步中最重要的是哪一步？
在软件测试的不同阶段中，每个环节都有其不可替代的价值，但若从工程效率和缺陷防控的全局视角来看，单元测试（Unit Testing） 是质量金字塔的基石，其重要性最为关键。以下是分层解析： 一、从缺陷修复成本看优先级 美国国家标准与技术研究院（NIST）研究显示： 单元测试阶段…...
QML和C++交互
目录 1 QML与C交互基础1.1 全局属性1.2 属性私有化(提供接口访问) 2 QT与C交互（C创建自定义对象，qml文件直接访问）3 QT与C交互（qml直接访问C中的函数）4 QT与C交互（qml端发送信号 C端实现槽函数）…...
试题速浏、分类及浅析)
2021年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2021年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛（China Undergraduate Mathematical Contest in Modeling）是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动，目的在于激励学生学习数学的积极性，提高学…...
mariadb使用docker compose方式安装
问题 本地mac m1上面的mysql和mariadb突然不用使用了，重新安装也不想，最近mac系统也更新了，brew也更新了，重新安装mariadb还是不能正常使用，现在我打算使用docker来安装本地的mariadb了。 默认配置文件my.cnf 从容器…...
Logo语言的死锁
Logo语言的死锁现象研究 引言 在计算机科学中，死锁是一个重要的研究课题，尤其是在并发编程中。它指的是两个或多个进程因争夺资源而造成的一种永久等待状态。在编程语言的设计与实现中，如何避免死锁成为了优化系统性能和提高程序可靠性的关…...
具身智能零碎知识点（一）：深入解析Transformer位置编码
深入解析Transformer位置编码 Transformer位置编码完全解析：从公式到计算的终极指南一、位置编码的必要性演示二、位置编码公式深度拆解原始公式参数说明（以d_model4为例） 三、完整计算过程演示步骤1：计算频率因子步骤2࿱…...
0201概述-机器学习-人工智能
文章目录 1、概述1.1、示例1.2、概念 2、应用场景2.1、行业应用场景2.1.1、金融领域2.1.2、 医疗健康2.1.3、零售与电商2.1.4、 制造业2.1.5、自动驾驶 2.2、功能场景分类2.2.1、 预测类2.2.2、分类与识别类2.2.3、生成与优化类 2.3、机器学习适用场景的共同特征 3、实现机器学…...
金能电力工具柜：“五世同堂”演绎创新华章
在电力与工业领域的浩瀚星空中，金能电力如同一颗璀璨的星辰，其工具柜产品更是经历了五代更迭，如同家族中的“五世同堂”，每一代都承载着前人的智慧与后人的创新，共同谱写着传承与创新的交响曲。 初识平凡：普…...
蓝桥杯每日刷题c++
目录 P9240 [蓝桥杯 2023 省 B] 冶炼金属 - 洛谷 (luogu.com.cn) P8748 [蓝桥杯 2021 省 B] 时间显示 - 洛谷 (luogu.com.cn) P10900 [蓝桥杯 2024 省 C] 数字诗意 - 洛谷 (luogu.com.cn) P10424 [蓝桥杯 2024 省 B] 好数 - 洛谷 (luogu.com.cn) P8754 [蓝桥杯 2021 省 AB2…...
MySQL基础 [五] - 表的增删查改
目录 Create（insert） Retrieve（select） where条件 编辑 NULL的查询 结果排序(order by) 筛选分页结果 (limit) Update Delete 删除表 截断表（truncate） 插入查询结果（insertselect&…...
深入解析 MySQL 中的日期时间函数：DATE_FORMAT 与时间查询优化
深入解析 MySQL 中的日期时间函数：DATE_FORMAT 与时间查询优化 在数据库管理和应用开发中，日期和时间的处理是不可或缺的一部分。MySQL 提供了多种日期和时间函数来满足不同的需求，其中DATE_FORMAT函数以其强大的日期格式化能力，…...
GPU是什么？ 与 FPGA 有何关联
前段时间，AMD 和英伟达相继接到通知将对我国断供高端 GPU 芯片，很多人这才意识到 GPU 的战略价值。那么 GPU 究竟是什么？它为何如此重要？今天就由 宸极教育 带大家一起了解 GPU 的核心地位，以及它与国产FPGA发展的关系…...
数据结构与算法：基础与进阶
🌟 各位看官好，我是maomi_9526！ 🌍 种一棵树最好是十年前，其次是现在！ 🚀 今天来学习C语言的相关知识。 👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更…...
低配置云服务器网站的高效防御攻略
在网络环境日益复杂的当下，低配置云服务器网站常面临攻击威胁。不少站长疑惑，明明设置了 CC 防御，服务器却依旧不堪一击，这是怎么回事呢？ 比如，在 CC 防御配置中，设定 10 秒内允许访问 50 次。但…...
使用 Lua 脚本高效查询 Redis 键的内存占用
使用 Lua 脚本高效查询 Redis 键的内存占用 在处理 Redis 数据时，我们常常需要了解某些键的内存占用情况，尤其是在优化内存使用或排查问题时。虽然 Redis 提供了MEMORY USAGE命令来查询单个键的内存占用，但如果需要批量查询多个键࿰…...
【Linux篇】基础IO - 揭秘重定向与缓冲区的管理机制
📌 个人主页： 孙同学_ 🔧 文章专栏：Liunx 💡 关注我，分享经验，助你少走弯路！ 文章目录 一. 理解重定向1.1 理解重定向1.2 dup21.3 进一步理解重定向输出重定向：追加重定向…...
centos 8 启动Elasticsearch的时候报内存不足问题解决办法
centos 8 启动Elasticsearch 的时候报错，导致无法启动Elasticsearch 。 [root@CentOS-8 ~]# journalctl -xe Apr 07 18:25:56 CentOS-8.0 kernel: [ 8754] 0 8754 3180 63 69632 0 0 sh Apr 07 18:25:56 CentOS-8.0 kernel: [ 8755] 0 8755 3180 64 69632 0 0 sh Apr 07 18:25…...
深入剖析Java IO设计模式：从底层原理到实战应用
🔍 引言：设计模式与IO的完美交响 在软件开发的浩瀚星河中，设计模式犹如璀璨的导航星，而Java IO体系则是支撑数据流动的神经网络。 当我们以设计模式的视角重新审视Java IO库时，会发现这个看似平凡的IO世界实则暗藏着…...
阶段测试 【过程wp】
分享总结： 回顾起来，真的感慨很多呀。看着并不难啊，但难的是解题思维：如何判断该页面的关键点，快速地确定问题的核心，找到对应的解决方法。达到便捷、高效的得到结果。我们做了整整近七个半小时。在这个过程中，我发现自己的思维钝化，不太能自主高效地划分判断漏洞类型，…...
qml信号与槽函数
目录 信号与槽函数基础方法1-使用Connections方式2-使用connect（不常用） 自定义组件与信号槽使用 信号与槽函数基础 方法1-使用Connections main.qml import QtQuick 2.15 import QtQuick.Window 2.15 import QtQuick.Controls 2.15Window {id:windoww…...
ngx_palloc
定义在 src\core\ngx_palloc.c void * ngx_palloc(ngx_pool_t *pool, size_t size) { #if !(NGX_DEBUG_PALLOC)if (size < pool->max) {return ngx_palloc_small(pool, size, 1);} #endifreturn ngx_palloc_large(pool, size); } 判断 需要分配的内存大小 是否小于 poo…...
notepad++日常使用（每行开头、每行末尾增加字符串，每行中间去掉字符串）
1. 每行开头增加字符串 如果我们要给下面的数据每行的开头都增加相同的一些字符串{value: 这时候只需要使用notepad的语法，使用快捷键Crtl H 替换功能，每一行开头使用 ^ 符号，替换成自己想要的字符串 {value: 使用全部替换就会在每行数据…...
Java面试黄金宝典39
1. SNMP、SMTP 协议 SNMP（简单网络管理协议） 定义：SNMP 是一种应用层协议，用于在 IP 网络中管理网络节点（如服务器、路由器、交换机等）。它允许网络管理员监控网络设备的状态、收集性能数据、进行故障诊断等操作。SNMP 基于 UDP 协议，采用轮询和事件驱动相结合的方式来收…...
如何解决：http2: Transport received Server‘s graceful shutdown GOAWAY
有一次做压力测试，客户端经常出现如下错误： http2: Transport: cannot retry err [http2: Transport received Servers graceful shutdown GOAWAY] after Request.Body was written; define Request.GetBody to avoid this error是 Golang 中使用 HTTP/…...
贪心算法（16）（java）俄罗斯套娃信封问题
题目：给你一个二维整数数组 envelopes ，其中 envelopes[i] [wi, hi] ，表示第 i 个信封的宽度和高度。 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算…...
【DeepSeek原理学习2】MLA 多头隐变量注意力
解决的问题 Multi-Head Latent Attention，MLA——解决的问题：KV cache带来的计算效率低和内存需求大以及上下文长度扩展问题。 MLA原理 MLA原理：其核心思想是将键（Key）和值（Value）矩阵压缩到…...
2024年RAG大赛
2024 CCF国际AIOps挑战赛赛题与赛制解读-CSDN博客 自动化测评也比较有意思，分数为 关键字 语义相似度，分值比为6:4. 2024 CCF AIOPS国际挑战赛优秀奖方案分享 https://zhuanlan.zhihu.com/p/7444390758 【大模型RAG获奖方案分享】如何提高RAG系统在…...
的一些内置函数与求和函数)
2025-4-6-C++ 学习 有序数组、set()的一些内置函数与求和函数
C的学习必须更加精进一些，对于好多的函数和库的了解必须深入一些。 文章目录 3510. 移除最小数对使数组有序 II（有序数组）题目参考代码（1）auto it idx.lower_bound(i);功能解释可能的使用场景常见错误 （2&…...
Flutter：Flutter SDK版本控制，fvm安装使用
1、首先已经安装了Dart，cmd中执行 dart pub global activate fvm2、windows配置系统环境变量 fvm --version3、查看本地已安装的 Flutter 版本 fvm releases4、验证当前使用的 Flutter 版本： fvm flutter --version5、切换到特定版本的 Flutter fvm use …...
GPT-4o 的“图文合体”是怎么做到的
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...
PyTorch教程：如何读写张量与模型参数
本文演示了PyTorch中张量（Tensor）和模型参数的保存与加载方法，并提供完整的代码示例及输出结果，帮助读者快速掌握数据持久化的核心操作。 1. 保存和加载单个张量 通过torch.save和torch.load可以直接保存和读取张量。 import to…...
MySQL8.0.31安装教程，附pdf资料和压缩包文件
参考资料：黑马程序员 一、下载 点开下面的链接：https://dev.mysql.com/downloads/mysql/ 点击Download 就可以下载对应的安装包了, 安装包如下: 我用夸克网盘分享了「mysql」，链接：https://pan.quark.cn/s/ab7b7acd572b 二、解…...
Linux 系统中对存储设备（/dev/mmcblk、/dev/sd、/dev/nvme）进行分区、格式化或挂载的操作
在 Linux 系统中对存储设备（/dev/mmcblk、/dev/sd、/dev/nvme）进行分区、格式化或挂载的操作步骤如下： 一、确认设备信息 首先明确要操作的设备名称（如 /dev/sdb、/dev/nvme0n1），避免误操作导致数据丢失&a…...
【Kafka基础】topics命令行操作大全：高级命令解析（1）
1 创建压缩主题（Log Compaction） /export/home/kafka_zk/kafka_2.13-2.7.1/bin/kafka-topics.sh --create \--bootstrap-server 192.168.10.33:9092 \--topic comtopic \--partitions 3 \--replication-factor 2 \--config cleanup.policycompact \--con…...
springboot集成spring loadbalancer实现客户端负载均衡
在 Spring Boot 中实现负载均衡，通常需要结合 Spring Cloud 组件，比如 Spring Cloud LoadBalancer。Spring Cloud LoadBalancer 是一个客户端负载均衡器，可以与 Spring Boot 集成，实现微服务之间的负载均衡。 以下是一个简单的示…...
什么是 k8s Affinity（亲和性）
在 Kubernetes（K8s）中，Affinity（亲和性） 是一种 Pod 调度策略，它用于控制 Pod 在什么条件下可以被调度到特定的节点上。它比 Taints 和 Tolerations 更灵活，可以基于 节点属性 或 Pod 之间的关系…...
深度探索：策略学习与神经网络在强化学习中的应用
深度探索：策略学习与神经网络在强化学习中的应用 策略学习(Policy-Based Reinforcement Learning)一、策略函数1.1 策略函数输出的例子 二、使用神经网络来近似策略函数：Policy Network ,策略网络2.1 策略网络运行的例子2.2需要的几个概念2.3神经网络近似…...
用VAE作为标题显示标题过短，所以标题变成了这样
VAE (Variational Autoencoder / 变分自编码器) 基本概念: VAE 是一种生成模型 (Generative Model)，属于自编码器 (Autoencoder) 家族。 它的目标是学习数据的潜在表示 (Latent Representation)，并利用这个表示来生成新的、与原始数据相似的数据。 与标…...