JustPureH₂O

斐波那契数列是一个很有意思的东西，它的每一项都由前两项的和导出，即对于 n\geq3，有 F_n=F_{n-1}+F_{n+2}。入门算法时，尤其是刚开始涉及递归函数时，你可能就已经写过求解斐波那契数列通项的函数了。基于递归的算法会将当前数分为两个较小的数，然后继续分解直到变为 F_1,F_2。一般来说，这样的算法复杂度是 \mathcal O(2^n) 的，极其不友好。我们会选择从定义出发，也就是使用循环结构来递推。等到了提高组，你会发现这个算法也不是最优的，稍微了解线性代数（此处尤指矩阵乘法）后，你会发现斐波那契数列的通项可以由下面这个矩阵递推式给出：

距离上次参加 CSP 已经过去了一年又五天，感觉一年以来自己收获了不少。

也叫高斯-若尔当消元法，简称高斯消元法或高斯消元。它可以在 \mathcal O(n^3) 的时间复杂度内求出矩阵方程组的解、以及给定矩阵的逆矩阵、行列式等。

访问 API 文档 以了解更多。

顾名思义，环就是环

对于一个正整数 n，它的阶乘等于 n\times(n-1)\times(n-2)\times\dots\times3\times2\times1=\prod\limits_{i=1}^{n}i，记作 n!。特殊地，{0!=1}。

《孙子算经》有云：

欧拉函数 \varphi(x)，表示 [1,x] 内与 x 互质的数的个数。对于质数 p 显然有 \varphi(p)=p-1。特殊地，\varphi(1)=1。欧拉函数是一个积性函数，对任意互质的数 a,b，都有 \varphi(ab)=\varphi(a)\cdot\varphi(b)。不互质时，如果 x 为奇数，那么有 \varphi(2n)=\varphi(n)。

众所周知的是，欧几里得算法可以用来求解最大公约数。它的核心是一个恒等式 \gcd(a,b)=\gcd(b,a\bmod b)，并且在 b=0 时函数值是 a。C++14 标准提供一个函数 __gcd() 来求解最大公约数，而在 C++17 以后，我们可以使用 gcd() 和 lcm() 函数来求解两个数的最大公约数和最小公倍数。

也就是说任何合数都可以唯一地表示成 p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_n^{c_n}=\prod\limits_{i=1}^np_i^{c_i}~(c_i\in\mathbb N_+) 的形式，这条定理在之后的质数筛中有大用。