当前位置: 首页 > news >正文

数论知识点总结(一)

文章目录

目录

文章目录

前言

一、数论有哪些

二、题法混讲

1.素数判断,质数,筛法

2.最大公约数和最小公倍数

3.快速幂

4.约数


前言

现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣!


一、数论有哪些

数论 原根,素数判断,质数,筛法最大公约数,gcd扩展欧几里德算法,快速幂,exgcd,不定方程,进制,中国剩余定理,CRT,莫比乌斯反演,逆元,Lucas 定理,类欧几里得算法,调和级数,欧拉降幂......

但是,可但是,但可是,我是个蒟蒻,只能胜任很简单的数论和算法,今天只是做个考前复习罢了

二、题法混讲

1.素数判断,质数,筛法

(1)素数,质数的定义:只能被一和他本身整除的正整数教素数,又称质数(2是素数,0和1却不是)

(2)判定

代码如下(示例):

bool isprime(int n){if(n<2) return false;int x=sqrt(n);for(int i=2;i<=x;i++)if(n%i==0) return false;return true;
}

(3)埃氏筛

代码如下(示例):

void get_primes(int n){for(int i=2;i<=n;i++){if(!flag[i]){p[++cnt]=i; for(int j=1;p[j]<=n/i;j++){flag[p[j]*i]=true;}}}
}

(4)线性筛

代码如下(示例):

void get_primes(int n){for(int i=2;i<=n;i++){if(!flag[i]){p[++cnt]=i;for(int j=1;p[j]<=n/i;j++){flag[p[j]*i]=true;if(i%p[j]==0) break;}}}
}

2.最大公约数和最小公倍数

代码如下(示例):

int gcd(int x,int y){if(y==0) return x;return gcd(y,x%y);
}
int lcm(int x,int y){return x*y/gcd(x,y);
}

3.快速幂

递归写法:

int ksm(int a,int b,int mod){if(!b) return 1;int t=ksm(a,b>>1,mod);return (LL)(b&1?a:1)*t%mod*t%mod;
}

非递归写法:

①
int ksm(int a,int b,int mod){int res=1;while(b){if(b&1) res=(LL)res*a%mod;a=a*a%mod;b>>=1;}return res;
}
②
int ksm(int a,int b,int mod){int ans=1;for(;b;a*=a,a%=mod,b>>=1)if(b&1) ans*=a,ans%=mod;return ans;
}

4.约数

代码如下(实例):

vector<int> d;
void solve(int n){d.clear();for(int i = 1; i <= n / i; i ++){if(n % i == 0){d.push_back(i);if(i != n / i) d.push_back(n / i);}}sort(d.begin(), d.end());for(auto x : d) cout << x << " ";
}


祝大家CSP-J/S,RP++

相关文章:

数论知识点总结(一)

文章目录 目录 文章目录 前言 一、数论有哪些 二、题法混讲 1.素数判断,质数,筛法 2.最大公约数和最小公倍数 3.快速幂 4.约数 前言 现在针对CSP-J/S组的第一题主要都是数论,换句话说,持数论之剑,可行天下矣! 一、数论有哪些 数论 原根,素数判断,质数,筛法最大公约数…...

知识分享 钡铼网关功能介绍:使用SSLTLS 加密,保证MQTT通信安全

背景 为了使不同的设备或系统能够相互通信&#xff0c;让旧有系统和新的系统可以集成&#xff0c;通信更加灵活和可靠。以及将数据从不同的来源收集并传输到不同的目的地&#xff0c;实现数据的集中管理和分发。 通信网关完美克服了这一难题&#xff0c;485或者网口的设备能通过…...

asp.net core mvc区域路由

ASP.NET Core 区域路由&#xff08;Area Routing&#xff09;是一种将应用程序中的路由划分为多个区域的方式&#xff0c;类似于 MVC 的控制器和视图的区域划分。区域路由可以帮助开发人员更好地组织应用程序的代码和路由&#xff0c;并使其更易于维护。 要使用区域路由&#…...

KNN(下):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

Servlet开发-session和cookie理解案例-登录页面

项目展示 进入登录页面&#xff0c;输入正确的用户名和密码以后会自动跳到主页 登录成功以后打印用户名以及上次登录的时间&#xff0c;如果浏览器和客户端都保存有上次登录的信息&#xff0c;则不需要登录就可以进入主页 编码思路 1.首先提供一个登录的前端页面&…...

Polygon Miden:扩展以太坊功能集的ZK-optimized rollup

1. 引言 Polygon Miden定位为zkVM&#xff0c;定于2023年Q4上公开测试网。 zk、zkVM、zkEVM及其未来中指出&#xff0c;当前主要有3种类型的zkVM&#xff0c;括号内为其相应的指令集&#xff1a; mainstream&#xff08;WASM, RISC-V&#xff09;EVM&#xff08;EVM bytecod…...

[题]宝物筛选 #单调队列优化

五、宝物筛选&#xff08;洛谷P1776&#xff09; 题目链接 好家伙&#xff0c;找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #include<bits/stdc.h> using namespace std; const int N 1e5 10; int f[N]; int n, m; int v, w, s; int l…...

.NET的键盘Hook管理类,用于禁用键盘输入和切换

一、MyHook帮助类 此类需要编写指定屏蔽的按键&#xff0c;灵活性差。 using System; using System.Runtime.InteropServices; using System.Diagnostics; using System.Windows.Forms; using Microsoft.Win32;namespace MyHookClass {/// <summary>/// 类一/// </su…...

Anaconda Jupyter

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言An…...

Unity中Shader的前向渲染路径ForwardRenderingPath

文章目录 前言一、前向渲染路径的特点二、渲染方式1、逐像素(效果最好)2、逐顶点(效果次之)3、SH球谐(效果最差) 三、Unity中对灯光设置 后&#xff0c;自动选择对应的渲染方式1、ForwardBase仅用于一个逐像素的平行灯&#xff0c;以及所有的逐顶点与SH2、ForwardAdd用于其他所…...

简历项目优化关键方法论-START

START方法论是非常著名的面试法则&#xff0c;经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务&#xff0c;你负责的做的是什么Action:动作&#xff0c;针对这样的情况分析&#xff0c;你采用了什么行动方式Result:结果&#xff0c;在这样…...

TensorFlow学习1:使用官方模型进行图片分类

前言 人工智能以后会越来越发达&#xff0c;趁着现在简单学习一下。机器学习框架有很多&#xff0c;这里觉得学习谷歌的 TensorFlow&#xff0c;谷歌的技术还是很有保证的&#xff0c;另外TensorFlow 的中文文档真的很友好。 文档&#xff1a; https://tensorflow.google.cn/…...

C++ 并发编程实战 第八章 设计并发代码 一

目录 8.1 在线程间切分任务 8.1.1 先在线程间切分数据&#xff0c;再开始处理 8.1.2 以递归方式划分数据 8.1.3 依据工作类别划分任务 借多线程分离关注点需防范两大风险 在线程间按流程划分任务 8.2 影响并发性能的因素 8.2.1 处理器的数量 8.2.2 数据竞争和缓存兵乓…...

设计模式8、装饰者模式 Decorator

解释说明&#xff1a;动态地给一个对象增加一些额外的职责。就扩展功能而言&#xff0c;装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件&#xff08;Component&#xff09;&#xff1a;定义一个抽象接口以规范准备收附加责任的对象 具体构件&#xff08;ConcreteCom…...

抖音开放平台第三方代小程序开发,一整套流程

大家好&#xff0c;我是小悟 抖音小程序第三方平台开发着力于解决抖音生态体系内的小程序管理问题&#xff0c;一套模板&#xff0c;随处部署。能尽可能地减少服务商的开发成本&#xff0c;服务商只用开发一套小程序代码作为模板就可以快速批量的孵化出大量的商家小程序。 第…...

Flutter笔记:滚动之-无限滚动与动态加载的实现(GetX简单状态管理版)

Flutter笔记 无限滚动与动态加载的实现&#xff08;GeX简单状态管理版&#xff09; 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq…...

前端架构师之02_ES6_高级

1 类和继承 1.1 class类 JavaScript 语言中&#xff0c;生成实例对象的传统方法是通过构造函数。 // ES5 创建对象 // 创建一个类&#xff0c;用户名 密码 function User(name,pass){// 添加属性this.name name;this.pass pass; } // 用 原型 添加方法 User.prototype.sho…...

VScode多文件编译/调试配置

之前都是在Visual Studio写C/C&#xff0c;最近想换到VScode&#xff0c;折腾半天把launch.json和tasks.json配好了&#xff08;虽然不懂为什么&#xff0c;但确实能用了&#xff09;&#xff0c;在此做个记录。 参考资料&#xff1a;1&#xff0c;2&#xff0c;3 环境&#…...

K折交叉验证——cross_val_score函数使用说明

在机器学习中&#xff0c;许多算法中多个超参数&#xff0c;超参数的取值不同会导致结果差异很大&#xff0c;如何确定最优的超参数&#xff1f;此时就需要进行交叉验证的方法&#xff0c;sklearn给我们提供了相应的cross_val_score函数&#xff0c;可对数据集进行交叉验证划分…...

2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版

#Go 1.21新增的 log/slog 完美解决了以上问题&#xff0c;并且带来了很多其他很实用的特性。 本次编译不使用log/slog 包 su - echo $GOPATH ;echo $GOROOT; cd /tmp; busybox wget --no-check-certificate https://go.dev/dl/go1.18.linux-amd64.tar.gz;\ which tar&&am…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...