素数筛
素数筛 暴力法 时间复杂度: O(n2)O(n^2)O(n2) 内层的 is_prime()is\_prime()is_prime() 函数使用遍历查找，其平均时间复杂度为 O(n2)O(\frac{n}{2})O(2n)，sieve()sieve()sieve() 函数同样使用遍历查找，时间复杂度显然为 O(n)O(n)O(n)，对于该算法的循环结构，平均时间复杂度为 O(n22)=O(n2)O(\frac{n^2}{2}) = O(n^2)O(2n2)=O(n2) 1234567891011121314def is_prime(num): if num < 2: # 直接排除 return False for i in range(2, num): # 遍历 if num % i == 0: return False return Truedef sieve(n): primes = [] for i in range(2, n + 1): if...
并查集
并查集 + Tarjan 算法 并查集是一种用于找出一个森林（图）中树（连通分支）的个数的算法，也可用于判断两个节点是否在同一棵树上。它在每一棵树（连通分支）上选择一个节点作为本棵树（连通分支）的代表。对于给定两个节点，如果他们具有相同的代表节点，则说明两个节点在同一个节点上。 一、并查集的简单应用 例题 1：城市群的数量 题目描述： 魔法大陆上有 n 个城市，编号为 1 到 n。城市与城市之间的道路均为双向道路，共有 m 条双向道路，并非任意两个城市之间都有双向道路。问，魔法大陆上有多少个城市群？ 若两个城市之间存在一条双向道路，则两个城市属于同一个城市群。任意两个城市之间最多只有一条双向道路。 输入格式： 第一行包含两个整数 n,m，含义与问题描述中相同。接下来 m 行，每行包含两个整数 u,v，表示城市 u 和城市 v 之间存在一条双向道路。 输出格式： 输出共一行，包含一个整数，表示城市群的数量。 代码示例： 123456789101112131415161718192021222324252627282930313233343536373839#...
基础数论
蓝桥杯基础数论学习笔记 目录： 素数（素数个数、最小素数，欧拉函数） 约数（约数个数公式） 幂 （快速幂） 阶乘 （阶乘的递推形式、阶乘与因数） 取模 （加减乘取模与除法取模、乘法逆元、中国剩余定理（待更新）） 异或与异或和 一、素数 素数又称质数，一个大于1且只能被1和它本身整除的数被称为素数。对素数的求解往往是解决素数和约数问题的基础。 （1）求解方法 素数的求解有试除法、埃氏筛和线性筛三种求法，其中线性筛效率最高，此处只列出线性筛代码，因为线性筛不仅效率高，还可以方便地求出每个数的最小质因数，用途更广。 注意在考试的时候尽量打表，蓝桥杯的内存限制比较宽，一般不会出现内存溢出。不要让素数的搜索占用宝贵的程序运行时间。 123456789101112131415161718# 线性筛def sieve(n): # find out all of the prime numbers between 2 and n prime = [] is_prime = [True]*(n+1) for i in range(2,n+1): if...