当前位置: 首页 > 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…...

YOLOv8鹰眼检测实战:无人机巡检场景下的目标识别应用

YOLOv8鹰眼检测实战&#xff1a;无人机巡检场景下的目标识别应用 1. 无人机巡检的视觉挑战与解决方案 在电力线路巡查、交通监控、农业勘测等场景中&#xff0c;无人机正成为不可或缺的空中巡检工具。然而传统人工分析航拍图像的方式存在效率低下、漏检率高、响应延迟等问题。…...

告别云端:在百元ESP32-S3上实现离线婴儿哭声识别,隐私与实时性我全都要

边缘智能革命&#xff1a;用ESP32-S3打造零隐私风险的婴儿监护终端 当科技与育儿需求碰撞&#xff0c;我们面临一个核心矛盾&#xff1a;如何在不牺牲隐私的前提下实现智能化监护&#xff1f;传统方案依赖云端处理&#xff0c;却让敏感数据暴露在传输与存储环节。本文将揭示一种…...

vue基于springboot的目的地旅游预订网站

目录同行可拿货,招校园代理 ,本人源头供货商功能模块划分技术实现要点扩展功能建议性能优化方向项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作同行可拿货,招校园代理 ,本人源头供货商 功能模块划分 用户模块 用户注册与登录…...

Qwen3-VL-8B系统资源管理:监控与清理GPU显存和C盘空间

Qwen3-VL-8B系统资源管理&#xff1a;监控与清理GPU显存和C盘空间 长期运行像Qwen3-VL-8B这样的大模型服务&#xff0c;就像养了一头“数字大象”——它能力强大&#xff0c;但胃口也不小&#xff0c;尤其能吃GPU显存和硬盘空间。很多朋友刚开始部署时一切顺利&#xff0c;但跑…...

mitmproxy实战:从环境搭建到HTTPS抓包全攻略

1. 认识mitmproxy&#xff1a;你的网络调试瑞士军刀 第一次听说mitmproxy时&#xff0c;你可能觉得这是个复杂的安全工具。但实际用过后就会发现&#xff0c;它就像网络调试领域的瑞士军刀&#xff0c;能解决各种数据抓包难题。简单来说&#xff0c;mitmproxy是个开源的交互式中…...

AutoRaise:macOS窗口悬停管理的技术实现与配置指南

AutoRaise&#xff1a;macOS窗口悬停管理的技术实现与配置指南 【免费下载链接】AutoRaise AutoRaise (and focus) a window when hovering over it with the mouse 项目地址: https://gitcode.com/gh_mirrors/au/AutoRaise AutoRaise是一款基于Objective-C开发的macOS窗…...

3步掌握AI模型训练:让新手也能玩转个性化Stable Diffusion模型

3步掌握AI模型训练&#xff1a;让新手也能玩转个性化Stable Diffusion模型 【免费下载链接】sd-trainer 项目地址: https://gitcode.com/gh_mirrors/sd/sd-trainer 在数字创意领域&#xff0c;AI绘画模型训练曾是一道高不可攀的技术门槛。设计师面对复杂的代码配置望而…...

Phi-4-reasoning-vision-15B快速上手:使用Postman完成图像问答API全流程调试

Phi-4-reasoning-vision-15B快速上手&#xff1a;使用Postman完成图像问答API全流程调试 1. 引言&#xff1a;认识视觉推理模型 Phi-4-reasoning-vision-15B是微软推出的新一代视觉多模态推理模型&#xff0c;它能像人类一样理解图片内容并进行智能问答。想象一下&#xff0c…...

RenderDoc实战:5分钟搞定OpenGL性能瓶颈定位(附Android联调技巧)

RenderDoc实战&#xff1a;5分钟定位OpenGL性能瓶颈的完整指南 移动端图形开发最令人头疼的瞬间&#xff0c;莫过于看到测试报告上"FPS波动大"的红色标记&#xff0c;却不知道从哪开始排查。上周团队里新来的工程师花了三天时间逐行检查着色器代码&#xff0c;最后发…...

RMBG-2.0多场景落地指南:短视频素材制作+电商主图抠图完整流程

RMBG-2.0多场景落地指南&#xff1a;短视频素材制作电商主图抠图完整流程 想快速给商品换个背景&#xff0c;又怕抠图不干净&#xff1f;想给短视频做个炫酷的片头&#xff0c;却被复杂的背景处理劝退&#xff1f;今天&#xff0c;咱们就来聊聊一个能让你彻底告别繁琐抠图的神…...