数论基础知识(上)

目录

数学符号

整除与约数

最大公约数(gcd)和最小公倍数(lcm)

质数 (素数)

算术基本定理(唯一分解定理)

约数个数

约数之和

分解质因数(枚举法)

试除法求约数(枚举法)

数学符号

x | y :整除符号,表示 x 整除 y ,也就是 x y 的约数,例如 2 | 4
整除与约数
a , b Z a = 0 ,若 k Z 满足 b = k × a ,那称为 b a 整除。记作 a | b ,否
a b
a | b ,则 b a 的倍数, a b 的约数。
最大公约数(gcd)和最小公倍数(lcm)
欧几里得算法
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
#include<iostream>
using namespace std;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {int c = gcd(a, b);return a * b / c;
}
int main() {int a, b;while (cin >> a >> b) {cout<< lcm(a, b) << endl;}return 0;
}

质数 (素数)
质数 ( 素数 ) ,是指在大于 1 的自然数中,除了 1 和它本身以外不再有其他约数的自然数。
试除法判定质数
bool isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i * i <= n; i ++) {
if (n % i == 0) {
return false;
}
}
return true;
}
算术基本定理(唯一分解定理)

推论——约数个数和约数之和

约数个数

#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int main()
{unordered_map<int, int> p;int n;cin >> n;while(n --){int x;cin >> x;for(int i = 2; i <= x / i; i ++)while(x % i == 0) p[i] ++, x /= i;if(x > 1) p[x] ++;}int ans = 1;for(auto i : p) ans = (long long)ans * (i.second + 1) % mod;cout << ans <<endl;return 0;
}
  1. 首先,定义了一个 unordered_map<int, int> p 用于存储不同质因数及其出现的次数。
  2. 读入整数 n ,表示接下来要处理 n 个数字。
  3. 在 while(n --) 循环中:
    • 读入每个数字 x 。
    • 通过 for 循环从 2 到 x 的平方根,检查每个数 i 是否能整除 x 。如果能整除,就增加质因数 i 在 p 中的计数,并不断用 x 除以 i ,直到 x 不能再被 i 整除。
    • 如果经过上述循环后 x 仍然大于 1 ,说明 x 本身就是一个质因数,增加其在 p 中的计数。
  4. 计算最终的结果 ans ,通过遍历 p 中的每个质因数及其计数,将每个质因数的计数加 1 后相乘,并对结果取模 mod 。
  5. 输出结果 ans 并结束程序。
约数之和

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{int n;cin >> n;unordered_map<int, int> p;while(n --){int x;cin >> x;for(int i = 2; i <= x / i; i ++)while( x % i == 0) p[i] ++, x /= i;if(x > 1) p[x] ++;}int res = 1;for(auto i : p){LL a = i.first, b = i.second, cnt = 1;while(b --) cnt = (long long)(cnt * a + 1) % mod;res = (long long)res * cnt % mod;}cout << res << endl;return 0;
}
  1. 在 main 函数中,首先读取一个整数 n ,表示接下来要处理 n 个输入的数。
  2. 定义了一个 unordered_map<int, int> p 来存储每个质因数及其出现的次数。
  3. 进入 while (n --) 循环,每次循环处理一个输入的数 x :
    • 从 2 到 x 的平方根进行遍历,如果 x 能被 i 整除,就不断将 p[i] 的计数加 1,并将 x 除以 i ,直到 x 不能再被 i 整除。
    • 如果经过上述循环后 x 仍然大于 1,说明 x 本身就是一个质因数,将其在 p 中的计数加 1 。
  4. 然后,通过遍历 p 中的每个质因数及其计数:
    • 对于每个质因数 a 和其计数 b ,初始化一个变量 cnt 为 1 。
    • 通过一个内层循环,每次将 cnt 更新为 (cnt * a + 1) % mod ,循环 b 次。
    • 将当前计算得到的 cnt 与 res 相乘,并对结果取模 mod ,更新 res 的值。
  5. 最后,输出计算得到的最终结果 res 并结束程序。
分解质因数(枚举法)
for (int i = 2; i * i <= n; i ++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i, cnt ++;
}
factor.push_back({i, cnt});
}
}
if (n > 1) {
factor.push_back({n, 1});
}
  • for (int i = 2; i * i <= n; i ++) :从 2 开始,到 n 的平方根为止进行循环。选择到平方根是因为,如果 n 有大于平方根的质因数,那么必然存在一个小于平方根的质因数与之对应,所以只需要检查到平方根就可以找出所有质因数。
  • if (n % i == 0) :如果 n 能被当前的 i 整除,说明 i 可能是 n 的一个质因数。
    • int cnt = 0; :初始化一个计数器 cnt 为 0,用于记录当前质因数 i 的出现次数。
    • while (n % i == 0) :通过这个内层循环,不断用 n 除以 i ,并增加计数器 cnt ,直到 n 不能再被 i 整除,从而确定质因数 i 在 n 的分解式中的指数。
    • factor.push_back({i, cnt}); :将质因数 i 及其指数 cnt 作为一个对存储到 factor 容器中。
  • if (n > 1) :如果经过上述循环,n 仍然大于 1,说明此时 n 本身就是一个质因数,且指数为 1 。所以将 {n, 1} 存入 factor 容器。
试除法求约数(枚举法)
vector<int> factor;
for (int i = 1; i * i <= n; i ++) {
if (n % i == 0) {
factor.push_back(i);
if (n / i != i) {
factor.push_back(n / i);
}
}
}

找出整数 n 的所有因数,并将它们存储在 vector<int> factor 中。

  • 外层的 for 循环从 1 开始到 n 的平方根。选择到平方根是因为对于一个数 n ,如果存在因数 i 小于等于 sqrt(n) ,那么必然存在另一个因数 n / i 大于等于 sqrt(n) ,所以只需要检查到平方根就能找出所有因数。
  • 对于每个 i ,如果 n 能被 i 整除,说明 i 是 n 的一个因数,将 i 放入 factor 向量中。
  • 然后检查 n / i 是否不等于 i 。如果不等,说明这是另一个不同于 i 的因数,也将其放入 factor 向量中。

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

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

相关文章

RTSP系列四:RTSP Server/Client实战项目

RTSP系列&#xff1a; RTSP系列一&#xff1a;RTSP协议介绍-CSDN博客 RTSP系列二&#xff1a;RTSP协议鉴权-CSDN博客 RTSP系列三&#xff1a;RTP协议介绍-CSDN博客 RTSP系列四&#xff1a;RTSP Server/Client实战项目-CSDN博客 目录 一、RTSP Server实战项目 1、准备 2、…

F4Pan网盘解析获取下载链接的工具系统源码

F4Pan网盘解析获取下载链接的工具系统源码&#xff0c;F4Pan(下称本项目)使用的接口全部来自于官方&#xff0c;无任何破坏接口的行为&#xff0c;本项目所有代码全部开源&#xff0c;仅供学习参考使用&#xff0c;请遵守相关的法律法规&#xff0c;禁止商用&#xff0c;若无视…

java+springboot+mysql校园二手书销售平台设计与实现00895-计算机毕业设计项目选题推荐(附源码)

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对校园二手书销售平台等问题&#xff0c;对校…

快速体验LLaMA-Factory 私有化部署和高效微调Llama3模型FAQ

序言 之前已经介绍了在超算互联网平台SCNet上使用异构加速卡AI 显存64GB PCIE&#xff0c;私有化部署Llama3模型&#xff0c;并对 Llama3-8B-Instruct 模型进行 LoRA 微调、推理和合并 &#xff0c;详细内容请参考另一篇博客&#xff1a;快速体验LLaMA-Factory 私有化部署和高…

计算机网络基础 - 计算机网络和因特网(2)

计算机网络基础 计算机网络和因特网Internet 结构和 ISP分组延时、丢失和吞吐量四种分组延时分组丢失吞吐量 协议层次及其服务模型概念数据单元&#xff08;DU&#xff09;协议栈TCP/IP 协议各层次的协议数据单元IOS/OSI 参考模型 计算机网络和因特网的历史早期计算机网路&…

自动驾驶的六个级别是什么?

自动驾驶汽车和先进的驾驶辅助系统&#xff08;ADAS&#xff09;预计将帮助拯救全球数百万人的生命&#xff0c;消除拥堵&#xff0c;减少排放&#xff0c;并使我们能够在人而不是汽车周围重建城市。 自动驾驶的世界并不只由一个维度组成。从没有任何自动化到完整的自主体验&a…

偷懒神器:auto 的讲解

1. auto 的定义 在c/c11之前&#xff0c;auto用来修饰局部变量&#xff0c;表明该变量是一个自动变量&#xff0c;函数结束后该变量销毁   c11中&#xff0c;赋予auto全新的含义。其中表示&#xff1a;auto不再是一个存储类型指示符&#xff0c;而是作为一个新的类型指示符来…

熊海1.0cmsPHP代码审计

熊海1.0cmsPHP代码审计 环境搭建 下载之后直接使用phpstduy搭建就好了 工具使用 比如使用seay审计系统 sql大多数是存在的&#xff0c;但是没有文件上传&#xff0c;这个就是需要自己去验证 漏洞审计 SQL注入 有点多&#xff0c;随便拿一个举例子 就比如我们的登录页面…

Ceres Cuda加速

文章目录 一、简介二、准备工作三、实现代码四、实现效果参考资料一、简介 字Ceres2.2.1版本之后,作者针对于稠密矩阵的分解计算等操作进行了Cuda加速,因此这里就基于此项改动测试一下效果。 二、准备工作 1、首先是需要安装Cuda这个英伟达第三方库,https://developer.nvidi…

日企的“目标式招聘”到底什么意思?

看到篇文章称&#xff1a;日企的目标式招聘&#xff0c;高效率招聘。这是什么意思呢&#xff1f;小编今天来跟大家讲一讲。 首先&#xff0c;日企的目标式招聘&#xff0c;其实企业也是迫不得已。一个大型企业的招聘负责人说&#xff1a;“以前我们都是认真地考察每一位应聘者&…

Vue 使用elementUI-plus el-calendar加 公历转农历 是否节假日 等

效果图&#xff1a; 1. 使用到自定文件 calendar.js /*** 1900-2100区间内的公历、农历互转* charset UTF-8* Author Jea杨(JJonlineJJonline.Cn)* Time 2014-7-21* Time 2016-8-13 Fixed 2033hex、Attribution Annals* Time 2016-9-25 Fixed lunar LeapMonth Param…

浏览器事件循环详解

1. 浏览器的进程模型 1.1. 何为进程&#xff1f; 程序运行需要有它自己的专属内存空间&#xff0c;可以把这块内存空间简单的理解为进程。 每个应用至少有一个进程&#xff0c;进程之间相互独立&#xff0c;即使要通信&#xff0c;也需要双方同意。 1.2. 何为线程&#xff1f…

NodeJS的安装【windows】

文章目录 1 安装包下载2 下载过程3 测试 1 安装包下载 Node.js中文网&#xff1a;https://nodejs.cn 2 下载过程 3 测试

【游戏引擎之路】登神长阶(八)——Python之旅行,休息一下,去看看新世界

5月20日-6月4日&#xff1a;攻克2D物理引擎。 6月4日-6月13日&#xff1a;攻克《3D数学基础》。 6月13日-6月20日&#xff1a;攻克《3D图形教程》。 6月21日-6月22日&#xff1a;攻克《Raycasting游戏教程》。 6月23日-7月1日&#xff1a;攻克《Windows游戏编程大师技巧》。 7月…

基于huggingface和langchain快速开发大模型应用

目录 一、HuggingFace. 2 1.1定义... 2 1.2活跃度... 2 1.3 工具集... 2 二、HuggingFace工具介绍... 3 2.1 Pipelines. 3 2.1.1定义... 3 2.1.2常见参数... 3 2.2、AutoClass. 4 2.2.1定义... 4 2.2.2 支持模型架构列表... 4 三、HuggingFace案例介绍... 4 3.1基…

Midjourney小技巧-提升出图质量的常用公式

一个公式让你的Midjourney生成更具韵味的人像身影图 step1-测试&#xff1a;输入提示词 - 一个面容精致的亚洲女性 - An Asian woman with a delicate face 生成的图片还是挺唯美的&#xff0c;就是过于单调&#xff0c;稀疏平常 step2-使用公式&#xff1a; 谁谁&#xff0…

flutter开发环境搭建与android studio 安装配置

flutter开发环境搭建与android studio 安装配置 安装 android studio 下载安装 Android Studio 开发工具 Android Studio官网安装的时看到配置路径就换成自己其他盘的路径即可&#xff0c;其他的一路下一步就ok安装完毕&#xff0c;运行打开缺少 android sdk 按照提示下载即可…

C++ 继承 派生类的运算符重载

C(二十二)派生类的运算符重载 语法赋值顺序引例1:当子类,不自实现赋值运算符函数重载时,默认调用父类的赋值运算符函数引例2:子类自实现赋值运算符函数重载,不做特殊处理时,只会调用父类的赋值运算符函数.引例3:子类自实现赋值运算符函数重载,在函数体内调用父类的赋值运算符函…

【leetcode】平衡二叉树、对称二叉树、二叉树的层序遍历(广度优先遍历)(详解)

Hi~&#xff01;这里是奋斗的明志&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f331;&#x1f331;个人主页&#xff1a;奋斗的明志 &#x1f331;&#x1f331;所属专栏&#xff1a;数据结构、LeetCode专栏 &#x1f4da;本系…

【Qt】如何搭建Qt开发环境

Qt的开发工具 需要搭建Qt开发环境&#xff0c;需要安装3个部分&#xff1a; C编译器&#xff08;gcc、cl.exe...&#xff09;注意&#xff0c;这里的C编译器不是指visual studio这种集成开发环境&#xff0c;编译器不等于IDE&#xff0c;编译器只是IDE调用的一个程序。Qt SDK…