EXGCD

　　我们在遇见不定方程的时候，总会一筹莫展，但是EXGCD为我们提供了方法，如同

　　$ a x + b y = c $

　　那么我们先从这个这个式子出发：

　　$ax+by=gcd(a,b)$ 　　 $(1)$

　　我们不妨设出另一个式子

　　$ b x_{0}+(a \% b)y_{0}=gcd(b,a \% b)$ 　　 $(2)$

euler函数

euler函数是表示从1~n中与n互质的个数，互质的定义简单提一下，$gcd(a,b)=1$。

那么如何求一个数的euler函数？

我们可以将每个数与n求gcd一下，如果gcd为1，则贡献加1，时间复杂度为 $O(n logn)$，极其优秀（雾）

那么来思考更加优秀的算法（为什么一定要求euler函数($\varphi(n)$函数)呢QAQ）

前置知识

　　1.线段树。。。

　　（好像没了

　　2.（可知可不知，可能会有帮助）动态开点线段树

主席树(可持久化线段树)

　　一看可持久化,我们总会想到一些恐怖的算法.但是其实理解并不难,而这里我只是将主席树的思想讲清楚(尽量),题还是自己刷(虽然我就没刷几道

　　先看一道 模板题

题目描述

如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

这篇博客只是简单叙述思想(因为ML太弱了),具体例题请转其他博客.

dsu on tree,许多OI将其归于启发式合并,当然如果你能理解更好,这只是一个理解方式罢了.

思想简述

　　顾名思义,这个算法是处理树上问题,将子树分开求解,如果暴力了话是枚举每个子树,然后dfs;

　　这里将每次dfs完的清空操作重新定义,并且规定dfs顺序,以来优化成log解法.

说实话,我真的对这个游戏看得是一脸懵逼,因为(我太弱了)我没有明白一些变量的意思,所以一直很懵,现在才明白,这让我明白博弈论(还可以骗钱)博大精深;

以下是我自己思考的过程,也许不严谨,但是最终明白了.

这里只是粗略地介绍Nim游戏,一个入门博客,以来更好地进入SG函数(因为我才刚学

游戏简介

　　背景故事我就不说了,直接介绍游戏规则.

其实网络流很久之前已经学过,但是因为一些原因搁置了很久,于是想再系统地复习一下.

由于博主能力有限,所以关于网络流知识也是了解个大概,这里只是简单介绍,并且说一下博主的感性理解

最大流

　　EK増广路算法

　　　　很容易理解的一个算法,也就是我们不断地bfs找出一条増广路然后更新剩余容量,直到更新完毕,类似于SPFA做法.时间复杂度$O(nm^{2})$;

前言

　　猫树,由猫锟发明,以简单的构造以及优秀的离线复杂度而出名,可以优秀地处理区间和问题;

　　前置知识:无;

简单思想

　　运用分治的思想,分别处理中点两边的信息,之后分类讨论,合并区间得出结果;

　　保存数据时运用完全二叉树的思想,逐层保存信息,有一定的层次性;

　　例题

　　简单意思即求区间最大和;

必备知识：

　　高斯消元，图论基本知识（好像就这。。。（雾））

这里是无向图部分，请不要走错场。。。

定义

　　我们将邻接矩阵定义为矩阵$A(u,v)$，我想邻接矩阵就不用再多说了；

　　我们将每个点的度数矩阵定义为矩阵$D(u,v)$，这里再加上数学表示；

　　$D(u,u)=u$这个点的度数，$D(u,v)=0（u!=v)$；

据说差分约束有很多种，但是我学过的只有SPFA求差分；

我们知道，例如 $A-B<=C$ ，那么这就是一个差分约束。

比如说，著名的三角形差分约束，这个大家都是知道的，什么两边之差小于第三边啦，等等等等。

所以说，我们学他干嘛（我们得出结论：学他没用，谢谢大家观看）

咳咳——说正事，我们来看一道例题：【luoguP1993】小K的农场：

LCA，最近公共祖先，这是树上最常用的算法之一，因为它可以求距离，也可以求路径等等

LCA有两种写法，一种是倍增思想，另一种是Tarjan求法，我们可以通过一道题来看一看，

例题

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？