本文经 @sLMxf 转载： 整除和余数 以下 $x、y、a$ 均为整数。 存在整数 $k$，使得 $x = ky$，则有 $y|x$（ $y$ 整除 $x$ ），若 $y>0$ 则称 $x$ 是 $y$ 的倍数，$y$ 是 $x$ 的因数。 如果 $x = ky + a$，则称 $a$ 为 $x/y$ 的余数，写作 $a = x % y...

写 P6623 [省选联考 2020 A 卷] 树 时发现根本不会，强制恶补。 如有不足，还请提出。 1.是什么请出老朋友并查集，并查集中有个优化为按两个并查集高度大小贪心的合并。 1234567void merge(int x,int y){ int fax=find(x),fay=find(y); if(siz[fax]<siz[fay])swap(fax,fay);//...

前言： 作者初学数论，如有不足还请指出。 基本概念定义$$\mu(x)=\begin{cases} 1&n=1或n 无平方因子且质因子个数为偶数\ 0&n 含有平方因子\ -1&n 无平方因子且质因子个数为奇数\end{cases}$$ 核心性质都挺巧妙的 1.莫⽐乌斯反演$$\sum_{d|n}\mu(d)=[n=1]...

顾名思义，建立在同余基础上的最短路。一般来讲，用于问凑数之类的问题时用，基本思想为 若有 $ax=b$，求 $b$ 的数量，则 $ax=b+kx$ 均为可行解。 1.跳楼机题目原址 如果你现在能到达第 $i$ 层，则 $i+kx$ 层均可到达，所以我们考虑在对 $x$ 取模的意义下建立多个点表示 $0-x$，从 $i$ 号点向 $(i+y)%x$ 与 $(i+z)%x$ ...

对于一些有限制次数的改变图上的边的题目，将原图复制若干份，也就是若干层，每层之间用特殊的边（题目给出的条件）连接起来，然后再跑最短路。 1.P4568 [JLOI2011] 飞行路线$k$ 条航线，我们便在原图的基础上再建立 $k$ 张子图，共 $k+1$ 张图，题目给出的特殊条件为转换边权使得其为 $0$，所以对于一条边 $(u,v,w)$，我们需要在第 $i、i+1$ 张图之间连一条 $...