纯小白蓝桥杯备赛笔记--DAY4(数学数据结构图论)

文章目录

    • 数学
      • 质因数分解
      • 辗转相除法求最大公约数
      • 最小公倍数:
      • 快速幂
      • 乘法逆元
        • 费马小定理
    • 逆元
    • 乘法逆元
      • 素数判定与埃式筛法
      • 朴素素数判定法
      • 埃式筛法
    • 图论
      • 并查集T3:真题--合根植物
      • Dijkstra
      • Floyd
    • 基础算法
      • 递归,循环,前缀和,差分
      • STL

数学

质因数分解

 int reduce(int prime[],int pn,int n,int rest[]){int i,k=0;for(i=0;i<pn;i++){if (n==1) break;if (prime[i]*prime[i]>n) {rest[k++]=n;break;}while(n%prime[i]==0){n/=prime[i];rest[k++]=prime[i];}}return k;}

解析:
这段代码是一个名为reduce的函数,它接受四个参数:一个整数数组prime[],一个整数pn表示数组的长度,一个整数n和一个整数数组rest[]。函数的目的是将整数n分解为质因数,并将这些质因数存储在rest[]数组中。

函数首先初始化两个变量i和k,其中i用于循环遍历prime[]数组,k用于记录rest[]数组的索引。

接下来,函数使用一个for循环遍历prime[]数组。在每次迭代中,它首先检查n是否等于1,如果是,则跳出循环。然后,它检查当前质数的平方是否大于n,如果是,则将n添加到rest[]数组中,并跳出循环。

如果当前质数的平方不大于n,则进入一个while循环。在这个循环中,只要n能被当前质数整除,就将n除以当前质数,并将当前质数添加到rest[]数组中。这个过程会一直重复,直到n不能被当前质数整除为止。

最后,函数返回k,即rest[]数组中的元素个数。

#include<bits/stdc++.h>
using namespace std;int main()
{int n,i;cin>>n;cout<<n<<"=";for(i=2;i<=n;i++){while(n!=i){if(n%i==0){cout<<i<<"*";n=n/i;}elsebreak;}}cout<<n<<endl;return 0;
}

辗转相除法求最大公约数

inline int gcd(int a,int b)
{if(a%b==0)return b;elsereturn (gcd(b,a%b));
}
  • 简单写法:
int gcb(int a,int b){return b==0 ? a:gcb(b,a%b);}

最小公倍数:

int lcm(int a,int b){return a/gcd(a,b)*b;//防溢出 , 很妙啊 ,大家可以记一下
}

快速幂

在这里插入图片描述

  • 模板
int qmi(int a,int b,int p)//对p取模
{int res=1;while(b)//只要b不为0,就一直迭代下去 {if(b&1)res=res*a%p;//b为奇数,乘一个a到答案里a=a*a%p,b>>=1;//底数平方,指数除以2 }return res; } 
  • 例题:数的幂次–1181
#include<bits/stdc++.h>
using namespace std;using ll =long long;ll qmi(ll a,ll b,ll p)//对p取模
{ll res=1;while(b)//只要b不为0,就一直迭代下去 {if(b&1)res=res*a%p;//b为奇数,乘一个a到答案里a=(ll)a*a%p,b>>=1;//底数平方,指数除以2 }return res; } int main(){int t;cin>>t;while(t--){ll n,m,p;cin>>n>>m>>p;cout<<qmi(n,m,p)<<endl;}return 0;}

乘法逆元

费马小定理

在这里插入图片描述

逆元

在这里插入图片描述

乘法逆元

  • 例题1:求乘法逆元
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int t,n;
ll p=1e9+7;
ll qsm(ll a,ll b)
{ll res=1;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res%p;
}
ll inv(ll x)
{return qsm(x,p-2);
}
int main()
{cin>>t;while(t--){cin>>n;cout<<inv(n)<<endl;}return 0;
}
  • 例题2:获胜的概率–3932
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
ll kmi(ll a,ll b)
{ll res=1;while(b){if(b&1) res=res*a%p;a=a*a%p;b>>=1;}return res%p;}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n,k;cin>>n>>k;if(k==0){cout<<1<<endl;for(int i=2;i<=n;i++) cout<<0<<endl;}else if(k&1){for(int i=1;i<=n;i++){if(i&1) cout<<0<<endl;else cout<<kmi(n/2,p-2)<<endl;}}else{for(int i=1;i<=n;i++){if(i&1) cout<<kmi((n+1)/2,p-2)<<endl;else cout<<0<<endl;}}return 0;}

素数判定与埃式筛法

朴素素数判定法

在这里插入图片描述

  • 例题:疑似素数-3334
#include<bits/stdc++.h>
using namespace std;
//求和
int f(int x)
{int res=0;while(x)res+=x%10,x/=10;return res;} 
bool isPrime(int n)
{if(n<2)return false;for(int i=2;i<=n/i;i++){if(n%i==0)return false;}return true;}
int main()
{int n;cin>>n;int ans=0;for(int i=1;i<=n;i++){if(isPrime(f(i)))ans++;}cout<<ans<<endl;
}

埃式筛法

在这里插入图片描述

bool vis[N];
vis[0]=vis[1]=true;//被筛掉了
for(int i=2;i<=n;i++)
{if(!vis[i])//如果i没有被筛掉,那么进行枚举for(int j=2*i;j<=n;j+=i)//枚举倍数 ,每次j变成i的倍数vis[j]=ture; } 
  • 例题2:小明的素数对–3205
#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
bool shai[N];vector<int> vec;//将素数筛中杂乱的质数变成排列有序的一个集合,用vector
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,ans=0;cin>>n;shai[0]=shai[1]=1;for(int i=2;i<=n;i++){if(!shai[i]){vec.push_back(i);for(int j=2*i;j<=n;j+=i) shai[j]=1;}}for(int i=0;i<vec.size();i++)for(int j=i+1;j<vec.size();j++){if(!shai[vec[j]-vec[i]]) ans++;}cout<<ans;return 0;}

图论

并查集T3:真题–合根植物

  • 并查集模版题:
  • 注意:不要调用string库。
  • 什么是并查集:处理不相交集合的合并问题。
  • 用途:求连通子图,求最小生成树的Kruskal算法和求最近公共祖先等。
  • 操作:
    • 初始化:
      在这里插入图片描述

    • 查询与合并:
      在这里插入图片描述

    • 查询时对路径进行压缩:
      在这里插入图片描述

    • 例题
      在这里插入图片描述

#include<cstdio>
#include<cstdlib>
using namespace std;
// 开始的时候定义数组 
#define MAXN 20001
int fa[MAXN];
//最好不要这样定义// 初始化
void init(int n)
{for(int i=0;i<=n;i++)fa[i]=i;} 
// 查询 int find(int x){
//         递归出口if(x==fa[x])return x;else{fa[x]==find(fa[x]);return fa[x];}}
// 合并
void unionn(int i,int j)
{int i_fa=find(i);// 找到i的祖先 int j_fa=find(j);// 找到j的祖先 fa[i_fa]=j_fa ;//i的祖先指向j的祖先 }  
// 写主函数
int main()
{int m,n,x,y,q;scanf("%d",&n);init(n);// 初始化这个数组scanf("%d",&m); //有m行for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);unionn(x,y);} scanf("%d",&q);// 输入q行 for(int i=1;i<=q;i++){scanf("%d%d",&x,&y);if(find(x)==find(y))printf("YES\n");elseprintf("NO\n");}return 0;         } 
  • 合根植物题解:这道题只有一个返回值,所以查询的时候注意不要增加一个返回值了。
#include<stdio.h>
int fa[1000005];
//初始化void init(int n){for (int i=1;i<=n;i++)fa[i] = i;}// 查询
int find(int x)
{if (fa[x] != x){int sx = find(fa[x]);fa[x] = sx;}return fa[x];
}// 合并void unionn(int i,int j){int i_fa=find(i);int j_fa=find(j);fa[i_fa]=j_fa;} 
int main(void)
{int m,n,q;scanf("%d%d%d",&m,&n,&q);init(m*n); int x,y;for(int i=0;i<q;i++){scanf("%d%d",&x,&y);unionn(x,y);}//计数器的设置int ans=0;for(int i=1;i<=m*n;i++){if(i==fa[i]){//一个数等于链条的祖先ans++; } }printf("%d\n",ans);return 0;
}

Dijkstra

在这里插入图片描述
在这里插入图片描述

Floyd

在这里插入图片描述

基础算法

递归,循环,前缀和,差分

添加链接描述

STL

添加链接描述

在这里插入图片描述

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

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

相关文章

ETL结合飞书快速实现业务信息同步

一、ETL工具介绍 ETLCloud数据集成平台是一款针对IT以及数据工程师推出的全域数据集成平台产品。它是集实时数据集成和离线数据集成以及API发布为一体的数据集成平台。与其他开源数据集成工具相比&#xff0c;系统采用轻量化架构、具有更快的部署速度、更快的数据传输速度、更…

什么是RMVB视频?如何把视频转成RMVB格式?视频格式转换的方法

一&#xff0c;什么是RMVB视频格式 RMVB是一种视频文件格式&#xff0c;它基于RealNetworks公司开发的RealMedia编解码器&#xff0c;被广泛应用于互联网上的视频流媒体传输和下载。RMVB文件通常具有较小的文件大小&#xff0c;同时保持较高的视频质量&#xff0c;因此在网络传…

【Kafka】Zookeeper集群 + Kafka集群

Zookeeper 概述 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 Zookeeper 工作机制★★★ Zookeeper从设计模式角度来理解&#xff1a; 1&#xff09;是一个基于观察者模式设计的分布式服务管理框架&#xff1b; 它负责存储和管理大家都关…

TDengine too many open files

too many open files 是比较常见的报错&#xff0c;尤其使用TDengine 3.0 集群时&#xff0c;大概率会遇到。这个报错很简单&#xff0c;但要想顺利解决&#xff0c;却涉及到很多知识点。 目录 知识点&#xff1a;fs.nr_open知识点&#xff1a;file-max & fs.file-nr知识点…

Intrigue Core:一款功能强大的攻击面枚举引擎

关于Intrigue Core Intrigue Core是一款功能强大的开源攻击面枚举引擎&#xff0c;该工具可以帮助广大研究人员更好地管理应用程序的攻击面。 Intrigue Core集成了各种各样的安全数据源&#xff0c;可以将这些数据提取到标准化的对象模型中&#xff0c;并通过图形数据库跟踪关…

2024认证杯数学建模A题保暖纤维保暖能力原创论文讲解(含完整python代码)

大家好呀&#xff0c;从发布赛题一直到现在&#xff0c;总算完成了认证杯数学中国数学建模网络挑战赛第一阶段A题目保暖纤维的保暖能力完整的成品论文。 本论文可以保证原创&#xff0c;保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品…

C++高级特性:柯里化过程与std::bind(六)

1、柯里化过程 1.1、operator()的引入 现在需要完成这样一个需求&#xff1a;有一个函数每次调用返回的结果不一样。例如&#xff1a;两次调用的返回值都不一样那么就可以达到这种目的 1.1.1、简单点的写法 可以给一个全局的变量&#xff08;静态变量&#xff09;&#xff…

SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测

SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测 目录 SCI一区 | Matlab实现INFO-TCN-BiGRU-Attention向量加权算法优化时间卷积双向门控循环单元注意力机制多变量时间序列预测预测效果基本介绍模型描述程…

实践笔记-linux内核版本升级(centos7)

linux内核版本升级 1.查看当前内核版本信息2.采用yum方式进行版本升级2.1导入仓库源2.2选择 ML 或 LT 版本安装2.3设置内核启动 3.删除旧版本内核 1.查看当前内核版本信息 #查看操作系统版本 cat /etc/redhat-release #查看系统内核 uname -r2.采用yum方式进行版本升级 2.1导…

紫光展锐—2024上海硬核科技企业百强榜TOP2,支撑新质生产力蓄势聚能

近日&#xff0c;在上海市经济信息化委员会指导下&#xff0c;上海市产业技术创新促进会联合市科协发布了《2024上海硬核科技企业TOP100榜单》。作为芯片科技创新的先锋&#xff0c;紫光展锐凭借在5G、AI、6G、卫星通信等前沿技术领域的持续创新&#xff0c;积极支撑新质生产力…

应急响应-战前反制主机HIDSElkeid蜜罐系统HFish

知识点 战前-反制-平台部署其他更多项目&#xff1a; https://github.com/birdhan/SecurityProduct HIDS&#xff1a;主机入侵检测系统&#xff0c;通常会有一个服务器承担服务端角色&#xff0c;其他主机就是客户端角色&#xff0c;客户端加入到服务端的检测范围里&#xff…

GMSSL-通信

死磕GMSSL通信-C/C++系列(一) 最近再做国密通信的项目开发,以为国密也就简单的集成一个库就可以完事了,没想到能有这么多坑。遂写下文章,避免重复踩坑。以下国密通信的坑有以下场景 1、使用GMSSL guanzhi/GmSSL进行通信 2、使用加密套件SM2-WITH-SMS4-SM3 使用心得 ​…

OSCP靶场-- Sybaris

OSCP靶场–Sybaris 考点(redis MODULE LOAD命令执行) 1.nmap扫描 ## ┌──(root㉿kali)-[~/Desktop] └─# nmap 192.168.158.93 -sV -sC -Pn --min-rate 2500 -p- Starting Nmap 7.92 ( https://nmap.org ) at 2024-04-11 04:24 EDT Nmap scan report for 192.168.158.93…

鸿蒙TypeScript学习第13天:【元组】

1、TypeScript 元组 我们知道数组中元素的数据类型都一般是相同的&#xff08;any[] 类型的数组可以不同&#xff09;&#xff0c;如果存储的元素数据类型不同&#xff0c;则需要使用元组。参考文档&#xff1a;qr23.cn/AKFP8k 元组中允许存储不同类型的元素&#xff0c;元组…

第四百五十六回

文章目录 1. 概念介绍2. 思路与方法2.1 实现思路2.2 使用方法 3. 内容总结 我们在上一章回中介绍了"overlay_tooltip用法"相关的内容&#xff0c;本章回中将介绍onBoarding包.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在本章回中介绍的onBo…

睿尔曼复合机器人之底盘操作流程

以操作流程为例&#xff0c;介绍底盘的操作流程。 开机&#xff1a;长按电源按钮&#xff0c;蜂鸣器短响两声&#xff0c;当第三声变长鸣后松开&#xff0c;等待机器开机。 使用&#xff1a; 建立通讯&#xff1a;主要采用无线WiFi与底盘进行通讯连接 无线连接方式&#xff…

docker最简单教程(使用dockerfile构建环境)

一 手里有的东西 安装好的docker+dockerfile 二 操作 只需要在你的dockerfile文件下执行命令 docker build -t="xianhu/centos:gitdir" . 将用户名、操作系统和tag进行修改就可以了,这就相当于在你本地安装了一个docker环境,然后执行 docker run -it xianhu/ce…

2024/4/5—力扣—下一个排列

代码实现&#xff1a; 思路&#xff1a;两遍扫描 void swap(int *a, int *b) {int t *a;*a *b;*b t; }void reverse(int *nums, int l, int r) {while (l < r) {swap(nums l, nums r);l;r--;} }void nextPermutation(int *nums, int numsSize) {int i numsSize - 2;wh…

循环新蓝海,“新”从“旧”中来

浙江安吉&#xff0c;是“两山”理念——“绿水青山就是金山银山”的发源地&#xff0c;也是众多循环经济和绿色产业的根据地。这里汇集了大批已上市和待上市的相关公司的总部&#xff0c;年初刚递表港交所的闪回科技&#xff0c;就是其中之一。 主营二手手机回收和销售的闪回…

关于nvm node.js的按照

说明&#xff1a;部分但不全面的记录 因为过程中没有截图&#xff0c;仅用于自己的学习与总结 过程中借鉴的优秀博客 可以参考 1,npm install 或者npm init vuelatest报错 2&#xff0c;了解后 发现是nvm使用的版本较低&#xff0c;于是涉及nvm卸载 重新下载最新版本的nvm 2…