数论知识点总结(一)
文章目录
目录
文章目录
前言
一、数论有哪些
二、题法混讲
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通信安全
背景 为了使不同的设备或系统能够相互通信,让旧有系统和新的系统可以集成,通信更加灵活和可靠。以及将数据从不同的来源收集并传输到不同的目的地,实现数据的集中管理和分发。 通信网关完美克服了这一难题,485或者网口的设备能通过…...
asp.net core mvc区域路由
ASP.NET Core 区域路由(Area Routing)是一种将应用程序中的路由划分为多个区域的方式,类似于 MVC 的控制器和视图的区域划分。区域路由可以帮助开发人员更好地组织应用程序的代码和路由,并使其更易于维护。 要使用区域路由&#…...
KNN(下):数据分析 | 数据挖掘 | 十大算法之一
⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ 🐴作者:秋无之地 🐴简介:CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作,主要擅长领域有:爬虫、后端、大数据…...
Servlet开发-session和cookie理解案例-登录页面
项目展示 进入登录页面,输入正确的用户名和密码以后会自动跳到主页 登录成功以后打印用户名以及上次登录的时间,如果浏览器和客户端都保存有上次登录的信息,则不需要登录就可以进入主页 编码思路 1.首先提供一个登录的前端页面&…...
Polygon Miden:扩展以太坊功能集的ZK-optimized rollup
1. 引言 Polygon Miden定位为zkVM,定于2023年Q4上公开测试网。 zk、zkVM、zkEVM及其未来中指出,当前主要有3种类型的zkVM,括号内为其相应的指令集: mainstream(WASM, RISC-V)EVM(EVM bytecod…...
[题]宝物筛选 #单调队列优化
五、宝物筛选(洛谷P1776) 题目链接 好家伙,找到了一个之前学习多重背包优化时的错误…… 之前记的笔记还是很有用的…… #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帮助类 此类需要编写指定屏蔽的按键,灵活性差。 using System; using System.Runtime.InteropServices; using System.Diagnostics; using System.Windows.Forms; using Microsoft.Win32;namespace MyHookClass {/// <summary>/// 类一/// </su…...
Anaconda Jupyter
🙌秋名山码民的主页 😂oi退役选手,Java、大数据、单片机、IoT均有所涉猎,热爱技术,技术无罪 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 获取源码,添加WX 目录 前言An…...
Unity中Shader的前向渲染路径ForwardRenderingPath
文章目录 前言一、前向渲染路径的特点二、渲染方式1、逐像素(效果最好)2、逐顶点(效果次之)3、SH球谐(效果最差) 三、Unity中对灯光设置 后,自动选择对应的渲染方式1、ForwardBase仅用于一个逐像素的平行灯,以及所有的逐顶点与SH2、ForwardAdd用于其他所…...
简历项目优化关键方法论-START
START方法论是非常著名的面试法则,经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务,你负责的做的是什么Action:动作,针对这样的情况分析,你采用了什么行动方式Result:结果,在这样…...
TensorFlow学习1:使用官方模型进行图片分类
前言 人工智能以后会越来越发达,趁着现在简单学习一下。机器学习框架有很多,这里觉得学习谷歌的 TensorFlow,谷歌的技术还是很有保证的,另外TensorFlow 的中文文档真的很友好。 文档: https://tensorflow.google.cn/…...
C++ 并发编程实战 第八章 设计并发代码 一
目录 8.1 在线程间切分任务 8.1.1 先在线程间切分数据,再开始处理 8.1.2 以递归方式划分数据 8.1.3 依据工作类别划分任务 借多线程分离关注点需防范两大风险 在线程间按流程划分任务 8.2 影响并发性能的因素 8.2.1 处理器的数量 8.2.2 数据竞争和缓存兵乓…...
设计模式8、装饰者模式 Decorator
解释说明:动态地给一个对象增加一些额外的职责。就扩展功能而言,装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件(Component):定义一个抽象接口以规范准备收附加责任的对象 具体构件(ConcreteCom…...
抖音开放平台第三方代小程序开发,一整套流程
大家好,我是小悟 抖音小程序第三方平台开发着力于解决抖音生态体系内的小程序管理问题,一套模板,随处部署。能尽可能地减少服务商的开发成本,服务商只用开发一套小程序代码作为模板就可以快速批量的孵化出大量的商家小程序。 第…...
Flutter笔记:滚动之-无限滚动与动态加载的实现(GetX简单状态管理版)
Flutter笔记 无限滚动与动态加载的实现(GeX简单状态管理版) 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq…...
前端架构师之02_ES6_高级
1 类和继承 1.1 class类 JavaScript 语言中,生成实例对象的传统方法是通过构造函数。 // ES5 创建对象 // 创建一个类,用户名 密码 function User(name,pass){// 添加属性this.name name;this.pass pass; } // 用 原型 添加方法 User.prototype.sho…...
VScode多文件编译/调试配置
之前都是在Visual Studio写C/C,最近想换到VScode,折腾半天把launch.json和tasks.json配好了(虽然不懂为什么,但确实能用了),在此做个记录。 参考资料:1,2,3 环境&#…...
K折交叉验证——cross_val_score函数使用说明
在机器学习中,许多算法中多个超参数,超参数的取值不同会导致结果差异很大,如何确定最优的超参数?此时就需要进行交叉验证的方法,sklearn给我们提供了相应的cross_val_score函数,可对数据集进行交叉验证划分…...
2023.09.30使用golang1.18编译Hel10-Web/Databasetools的windows版
#Go 1.21新增的 log/slog 完美解决了以上问题,并且带来了很多其他很实用的特性。 本次编译不使用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…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
