题意

原题地址：Codeforces

一句话题意：有三种颜色的点，现在要在这些点之间连边权为1的边，同种颜色的点之间的距离要不少于3，求合法的方案数。

定理内容

$$ p是素数\Leftrightarrow (p-1)!\equiv-1\ (\text{mod}\ p) $$

证明（口胡）

考虑$[1,p-1]$内的所有整数，他们在$\text{mod}\ p$意义下一定是有逆元的，且他们的逆元一定是小于等于p的

作用

在$O(n)$时间内求出$1-n$在$\text{mod}\ p$意义下的所有逆元

呐。。第一次出题。。。 感谢mk，wcg，kZime，zf验题 感谢zf提供T3 本文链接：https://margatroid.xyz/2017-09-29-contest-20170929-solve/

题意

luogu上的LCA模板题

可是这个题却没有模板题的自觉，作为一道模板题卡常卡的厉害

以前写倍增的时候就被恶心过一次，这次写树剖时又被恶心一次qwq

题目描述

原题地址：COGSCH

题目描述

原题地址：luogu

一句话题意：求$\sum_{i = l}^ri-\varphi(i)$。其中，$l,r\leq 10^{12}$

假的假的，世界都是假的

定理内容

关于$x,y$的二元一次方程$ax+by=m$有解，当且仅当$m$是$d$的整数倍，其中，$d=\gcd(a,b)$

读完上面这句话，你一定会觉得这是什么辣鸡定理，感觉好没用的样子。

其实裴蜀定理还用后半部分。

定理

设正整数 $m_1,m_2,⋯,m_n$ 两两互质，则同余方程组

$$ \begin{cases} x\equiv a_1(\mod m_1)&(1)\
x\equiv a_2(\mod m_2)&(2)\
\cdots\
x\equiv a_n(\mod m_n)&(n)\
\end{cases} $$