东灯的寒舍

人越是长大，越是想把自己藏起来。

“为什么要藏？藏在哪里？”你如此问。

“因为人靠秘密度日。”我如此答。

很久之前就想写一篇这个文章了，但是一直没抽出时间。

今天下午刚好颓废没事做，我们来聊聊这个话题吧。

线性筛是数论中主要的算法，在求素数、配合算数基本定理求积性函数中有重要作用。

本文研究线性筛和和线性筛的具体应用。

本文在2022年~2023年多次修订，最后一次修订在2023/8/21，如文章有错误请及时反馈。

Tarjan 算法自提出以来，一直作为图论的经典算法被众多 coder 学习。

最近重新摸回 Tarjan，才发现自己对 Tarjan 的实质根本就不理解，仔细学习后作一篇文章来记录。

圆方树是解决一类仙人掌问题的优秀方法。

广义圆方树是解决无向图路径问题的优秀方法，思路简单暴力且优雅。

这篇文章并不讨论解决仙人掌的圆方树，而是介绍广义圆方树和题目。

差分约束

建边套路

$$A≤B \ \ \ \rightarrow \ \ \ A-B≤0$$ $$A≥B \ \ \ \rightarrow \ \ \ B-A≤0$$ $$A<B \ \ \ \rightarrow \ \ \ A - B ≤ -1$$ $$A=B \ \ \ \rightarrow \ \ \ A-B≤0\&\&B-A≤0$$ $$A-B≥C \ \ \ \rightarrow \ \ \ B-A≤-C$$ $$B-A≥C \ \ \ \rightarrow \ \ \ A-B≤-C$$ $$A-B \le C \ \ \ \rightarrow \ \ \ B-A\ge -C$$ $$B-A \le C \ \ \ \rightarrow \ \ \ A-B\ge -C$$

过分简单的一道数论题，然而想了很长时间才做出来，记录一下。

问题为求：

$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}的整数解x的个数$$

整理一些数学基础知识。

Native

中国剩余定理用于求解线性同余方程组。

描述为：

设自然数 $m_1,m_2,m_3,…,m_r$ 两两互质，并记 $M=\prod^r_{i=1}m_i$，则

Native

若 $a × x \equiv 1(mod \ b)$，$a，b$ 互质，则称 $x$ 为 $a$ 的逆元，记为 $a^{-1}$。

逆元用于计算 $t/a \ mod \ b$ 时，转化为 $t×a^{-1} \ mod \ b$。

求逆元

拓展欧几里德

有一个在线性同余方程部分没有记录的性质：

$$ax+by=c \ \leftarrow\rightarrow \ a×x\equiv c(mod \ b)$$