【算法介绍】欧几里得算法
算法简介：时间 与 智慧欧几里得算法，简称 $\gcd$ ，常用的是辗转相减或辗转相除，是一个远古时期就被前人证明出来的算法。还有就是拓展欧几里得算法简称 $\tt exgcd$ ，是一个基于欧几里得算法用于求解 $Ax+By=C$ 方程的算法。非常的玄学，接下来会讲讲关于这些算法的流程代码以及复杂度分析。
算法演示：影照浮世风流欧几里得算法：旧语新知 · 记忆中的沙丘欧几里得算法，就是中国的辗转相减或辗转相除，本质上是让两个数不断地大数减小数（或者是用小数模大数），最后求出最大公约数，那么为什么会是这样呢？看如下证明
设一个 $a, b, c$ 分别表示 $\gcd(a,b) = \gcd(b,c)$ 这样一个式子的一部分，令他们三满足关系 $a=b\times q_0+c$（ $a$ 除以 $b$ 的余数是 $c$ ）如果 $b,c$ 有一个公因子 $q_1$ ，则这两个数可以有如下表示方法：$$b=k_0\times q_1,c=k_1\times q_1$$将其带入式子 $a = b\times q ...
【算法介绍】素数筛法
算法简介：骑士团长的一日假期素数筛法是作为数论基础而出现的。数论本质上是对数字的一些性质的研究，而质数是这里很重要的一部分。不同的质数筛有着不同的特性，用来解决不同的题目，接下来我们会大概了解几种。
算法演示：若困你于无风之地$O(\sqrt n)$ 判断单个质数这个很简单，由于考虑到因子是一对一对的，所以一对因数中较小的那一个最多最多是 $\sqrt n$ ，也就是说我们只需要枚举 $2$ ~ $\sqrt n$ 复杂度 $O(\sqrt n)$ ，不枚举 $1$ 是因为所有数字都是 1 的倍数，素数也只是被 $1$ 和它本身整除。
1234567bool isPrime(int x) { if(x <= 1) return false; for(int i = 2; i * i <= n; i++) { if(x % i == 0) return false; // 找到一个不是 1 也不是它本身的因子 } return true;}
$O(n\log\log n)$ 多个快筛这个就属于新开 ...
【拾题杂谈】517八段第二课F
题面题目链接大秦 为你打开 题目传送门
备用题面一个无向图中有n顶点和m条边，无重边无自环。顶点从1到n编号。
Q次询问，每次询问u,vu,v之间是否存在一条长度为奇数的简单路径。
注：简单路径为不经过重复的点的路径。
思路我们思考如何才能有一个长度为奇数的简单路径：
本来就有
有奇环。
为什么说是有奇环呢？不是说不能经过重复点吗？这里指的其实是经过的路径上有奇环，因为奇环可以分成两边走，由于是奇环，所以两边的奇偶性一定不一样，这样就给了我们选择路径奇偶性的余地。
那么本来就有是什么情况呢？如果两个点在一个 Dfs 生成树上面的深度奇偶性不同，那么他们就属于本来就有奇数路径。因为这样的话 $u\rightarrow root\rightarrow v$ 这样的路径一定是奇数的简单路径。那么如果奇偶性一样怎么办，那么我们就只能指望于两个点到他们 LCA 的路径上有奇环了。不难发现只要至少有一个奇环我们就是可以的。那么就只需要另外处理一个倍增数组，记录这里奇环的数量就可以了。
那么处理奇环也很简单，Tarjan 做点双连通分量，一个没有割点的图绝对有环，我们只需要判断是不是奇环，然后用 ...
【拾题杂谈】LuoguP3627 抢掠计划
题面大秦为你打开题目传送门
题目描述Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。
Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。
使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。 例如，假设该城中有 $6$ 个路口，道路的连接情况如下图所示：
市中心在路口 $1$，由一个入口符号 → 来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢劫的现金总数为 $47$，实施的抢劫路线是：$1-2-4-1-2-3 ...
【算法介绍】连通分量
算法简介：晨露浮光之思首先声明一点：这篇文章所谓 “连通分量” 并不是指一个算法，而是指算法 $\tt Tarjan$ 和 $\tt Kosaraju$ 算法，他们所应用的点双连通分量，边双连通分量，强连通分量，割点和桥，以及缩点。
我个人认为，$\tt Tarjan$ 算法只是一个思想，他的核心在于定义 $\tt low$ 和 $\tt dfn$ 数组的一系列性质的应用，还有在处理这些数据的过程中处理别的数据。接下来我们会依次介绍这些东西是怎么求的。
算法演示：千式齐聚之法Tarjan算法：真正的宝物我们在这里简单的介绍一下 Tarjan 的一个思想。
他首先对于一张图做 Dfs，得到的顺序叫做 Dfs 序，得到的图叫做 Dfs 树。
而对于每一个点被访问的顺序，也就是他第一次被访问的位置，我们用数组 $\tt dfn$ 表示，为什么要这样做呢？我们可以用一张图来简单看一看。我们这里就分为有向图和无向图来看。下图中数字是 Dfs 序。
有向图图例
边种类介绍
我们这样已经把这样的一个有向图变成了 Dfs 树的外观。我们按照这样一颗树的常见形式，将其分为如下几种边：1. ...
【拾题杂谈】517八段第二课D
题面题目链接大秦 为你打开 题目传送门
备用题面一个有向图中有 $n$ 顶点和 $m$ 条边，顶点从 $1$ 到 $n$ 编号。
给定起点 $s$ ，问最少要添加多少条边，才能使得s到其它所有顶点都有可达路径。
思路我们就只需要看我不可达的点可以到达多少我不可达的点，然后选择到达我不可达的点多的点，把他们标记成我可达的点，一直贪心下去即可。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast&quo ...
【拾题杂谈】517八段第二课C
题面题目链接大秦 为你打开 题目传送门
备用题面求割点。
思路那么这道题既然是求割点的模板题，我们就来浅浅回顾一下 Tarjan 求割点是怎么回事。
对于 Tarjan 最最基础的一些变量定义，不知道建议直接 出门右转看我 Tarjan 博文
那么言归正传，其实说割点就是 low 值大于 dfn 值，因为如果我最小的点就是到达我的子孙方向的，那么我就是必经之路，所以这个点就是割点。另外这个点如果是根要特判，如果这个根有大于等于 2 的儿子，那么它还是割点。
代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#pragma ...
【拾题杂谈】517八段第二课B
题面题目链接大秦 为你打开 题目传送门
备用题面给定一个 $N$ 个顶点，$M$ 条边的无向连通图，顶点从 $1$ 到 $N$ 编号。
问至少要添加几条边，才能使其变为双连通图。
思路这道题目不难想到缩点以后，找到度为 $1$ 的点（因为这样一切就断了）然后这样点的个数我们要把他们连到一起，答案就是这样点的数量除以二去上底。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131#pragma GCC optimize(2)#pragma GCC optimize(3, &q ...
【拾题杂谈】HDU4582 Spanning Tree
题面大秦为你打开题目传送门
题目描述给定一个 $N$ 个顶点 ，$M$ 条边的无向连通图，顶点从 $1$ 到 $N$ 编号。
再给出一个 $\tt dfs$ 生成树。
现在要求从 $\tt dfs$ 生成树中选最少的边集合 $S$ ，使得图中每一个简单环中最少有一条边属于 $S$ 。
题解这道题目就是记录每一个点可以到达的点的集合，如果可以到达父亲节点算作一个答案
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast", "inline")#include< ...
【拾题杂谈】517八段第一课G
题面题目链接大秦 为你打开 题目传送门
备用题面给一棵 $n$ 个节点的树, 节点编号为 $1$ ~ $n$ ，每条边有权值。
对于一棵树，最长的路径为树的直径，可能不唯一。
求该树的直径长度是多少，以及有多少条边满足所有的直径都经过该边。
思路首先直径肯定都会算，我们记录一个答案，把直径的一个端点作为根建树，然后对于每一个点记录一下该节点的子树中到根节点最远的是多远，顺便记录一下一共有几个，如果当前点是直径上的点的话我们先判断一下是否存在两个及以上最长路径，如果是的话答案缩小到深度减一，如果存在子树中到根节点的距离的最大值等于根节点到该点的距离，我们直接将答案减去深度减一直接输出即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210 ...
