【奇技淫巧】欧拉函数与欧拉定理
文章总览：坠临万界的星芒欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数，并且自身携带欧拉名称加持各种优良性质，被广泛的运用到各个数学推导方面；而欧拉定理更是必不可少，计算逆元是它最基本的运用，它也是凌驾于费马小定理的存在（费马小定理可以从欧拉定理中得出）；并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围，等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。
欧拉函数推导
欧拉函数性质
欧拉函数的计算
欧拉函数拓展
欧拉定理推导
拓展欧拉定理推导
概念基础：因缘假合的人身
欧拉函数推导
欧拉函数性质
欧拉函数基础推导关于欧拉函数，就从最基础的开始讲起。我们定义函数 $\varphi(n)$ 表示从 $1$ 到 $n$ 的数字中与 $n$ 互质的有多少个。这就是欧拉函数所表示的信息。那么关于欧拉函数我们能有什么已知的值吗？
非常显然的，对于一个质数 $p$，其欧拉函数值 $\varphi(p)=p-1$ 这是显然的，因为 $p$ 作为质数显然与 $1\sim p$ 之间的除了它本身以外任何数字互质。其次有一个容易让人纰漏的点，那就是 $\varphi(1 ...
【算法介绍】排列组合问题汇总
文章总览：远行雪杖的清晨排列组合，这是初赛题目和复赛数学题目中必不可少的一部分，同时也是大多数计数类 DP 的重难点所在。其特点就是各种题目百出不厌，千变万化，让人措不及防，但是实际上中国有句古话叫做“万变不离其宗”，排列组合的问题也是有一定套路可言的。本篇文章旨在总结大多数类型的排列组合基础模型以及使用方式，排列组合问题计算时几个常见的思考方向，等等等。下为文本大纲：
组合数基础
二项式定理
隔板法基础
组合数例题
排列数基础
错位排列
圆排列
多重集合排列
康托展开
排列组合综合应用
组合基础：便携炉具的正午
组合数基础
二项式定理
隔板法基础
组合数基础推导组合数大家绝对不陌生，组合数指的就是 $n$ 个数里面选出 $m$ 个，不考虑取出的顺序，有几种取法，这个取法的方法数量就是大家常见的 $C_n^m$。
举个最常见的例子，我有 $6$ 个数字，我要从中选出 $3$ 个，那么他表示成刚刚的符号就是 $C_6^3$，但是问题是如何计算呢？非常显然的，如果我们考虑取数的顺序，那么计算出来的就是排列数，我们划去排列即可。
具体的，第一个数字有 $6$ 种取法，第二个数字就少了一 ...
【算法介绍】中国剩余定理及其拓展
文章总览：穷高极天，亢盈难久中国有句古话：“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”上过小学一年级的我们都知道，这是非常经典的同余方程组，而它的解法，就是这篇文章要讲的中国剩余定理 $\tt Chinese\ Remainder\ Theorem$。
本文内容限定于下：
中国剩余定理证明
中国剩余定理实现
拓展中国剩余定理证明
拓展中国剩余定理实现
推导其一：威制八毒，灭却炎烟
同余方程的计算&通解形式
通解形式正确性证明
从实例出发的推导那么从开篇提到的“物不知数”问题出发，我们可以得到下面的同余方程组：
\begin{cases}
x\equiv 2\pmod 3\\
x\equiv 3\pmod 5\\
x\equiv 2\pmod 7
\end{cases}其实这个题目很早就有了答案，“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”这是来自于明朝数学家程大位在《算法统宗》中的解答口诀。其含义即是关于这个问题的通解形式，其中第一个字的表示模数，最后一个词中的数字表示每一个同余方程余数要乘以的系数，最后加起来模 $10 ...
517九段第三课 A ：整数分块 again
题面：整数分块again大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
给出 $N$ 并计算下面表达式的值：
\sum_{i=1}^N i^4\left\lfloor\frac{N}{i}\right\rfloor答案对于 $M$ 取模。
思路拿到题面，注意到整数分块的经典部分，不难写出如下代码：123456789inline void Work() { ll ans = 0; for(ll l = 1, r = 1; r <= n; l = r + 1) { r = n / (n / l); (ans += ((f(r) - f(l - 1) + P) % P) * (n / l) % P) %= P; if(r == n) break; } printf("%lld\n", ans);}
那么这题主要的考点，其实就是计算一段区间内的四次方和。借助强大的搜索引擎我们可以轻松知道四次方和前缀和公式是：
\cfrac{n(n+1)(2n+1) ...
517九段第一课 E ：求和
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
对于给定的 $N$，定义 $S(k)$ 为 $(x_1,x_2,…,x_k)$ 的数量。$(x_1,x_2,…,x_k)$ 满足以下条件：
$(x_1,x_2,…,x_k)$ 为正整数
$x_1+x_2+…+x_k=N$
现在需要你找到 $(S(1)+S(2)+…+S(N)) \bmod 10^9+7$
思路不难注意到对于 $N$ 而言 $S(k)=C_{N-1}^{k-1}$，我们要求的式子就可以化为 $\sum_{i=0}^{N-1}C_{N-1}^i=2^{N-1}$。但是 $N$ 特别大，大到需要高精度怎么办？快速幂显然不行，注意到 $2^{P-1}=1\pmod P$ 所以不断地从 $N$ 中提取出 $P-1$ 即可。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include<bits/stdc++.h>using namespa ...
517九段第一课 D ：不互质的数
题面：不互质的数大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
求 $1\sim N-1$ 中与 $N$ 不互质的数的和并对 $1e9+7$ 取模。
思路注意到 $k$ 与 $N$ 互质时，$N-k$ 也与 $N$ 互质，满足对称性，则利用类似等差数列求和的思路，可得 $n\times \varphi(n)/2$ 就是与 $N$ 互质的数的和，从总量减去即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc++.h>using namespace std;typedef long long ll;// typedef __int128 int128;typedef pair<int , int > pii;typedef unsigned long long ull;namespace FastIO { ...
517九段第一课 B ：解方程
题面：解方程大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
计算关于 $x, y$ 方程 $Ax+By+C=0$ 满足 $x_1\le x \le x_2,y_1\le y\le y_2$ 的整数解有多少个，其中给出 $A,B,C,x_1,x_2,y_1,y_2$ 并保证 $x_1\le x_2,y_1\le y_2$。
思路注意到方程可以化简为 $Ax+By=-C$，拓展欧几里得可以解决问题 $Ax+By=\gcd(A,B)$ 的问题，所以将方程中的未知数整体提取 $\frac{-C}{\gcd(A,B)}$，拓欧解出特解后乘回去，最后通过拓欧一般解计算公式
x = x_0 + \cfrac B {\gcd(A,B)} \times k ,y = y_0 - \cfrac A {\gcd(A,B)} \times k\quad(k ∈ Z)最后计算出合理的新的 $x,y$ 上下界即可。
关于无解和特解情况看代码。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
【算法介绍】网络流相关
算法总览：散勇化晓摸幺鱼简单的来说，网络流问题，就是给出一张图，图上面有一个起点，被称作“源点”，还有一个终点，被称作“汇点”。而每一条边都有一个容量，超过容量就不可以通过这条边，有时候边还会有费用，通过这条边就需要花费这些费用。最终的目的就是从源点出发，不管你用什么方法走，最终汇集到汇点的流量最大、或者流量最大中的方案中费用最小的等等等等……这类问题，全都被称作为网络流问题或者流量问题，在生活中应该是非常常见的一种问题。
本文内容限定大纲如下：
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
最大流计算之 $\tt FF$ 方法
最大流计算之 $\tt EK$ 算法
最大流计算之 $\tt Dinic$ 算法
最大流计算之 $\tt Dinic$ 算法优化
最小割计算之最大流最小割定理
最小割计算之割集与变种
费用流计算之算法推导
算法基础：棋秤作枕好入眠
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
网络流基本概念OK啊各位，虽然一开始的文章总览提到了网络流问题的基础概念，但是这里还是补充一下详细的定义以及一些符号 ...
【算法介绍】杜教筛和 Min_25 筛
文章总览：童年虽然但是，我们熟知的筛法应该是欧拉筛和埃式筛等筛质数的筛，属于直观意义上的“筛子”；我们也知道，欧拉筛其实是可以筛积性函数的；但是这次的两个筛不太一样，他们的作用是在于快速计算积性函数前缀和，不过他们的实现手法和思想与这些直观意义上的筛子相近，所以也被称为“筛”。
下面是本文大纲：
狄利克雷卷积的定义与性质
狄利克雷卷积的两个重要结论
常见的积性函数及其计算方式
线性筛筛积性函数的推导
线性筛常见应用二则
杜教筛的推导
杜教筛的常见应用二则
Min_25 筛的推导
Min_25 筛的常见应用一则
前置知识：邂逅
狄利克雷卷积的定义与性质
狄利克雷卷积的两个重要结论
常见的积性函数及其计算方式
狄利克雷卷积基础狄利克雷卷积的定义非常简单，就是对于两个数论函数 $f(x),g(x)$，他们狄利克雷卷积后的结果 $h(x)$ 定义为：
h(x)=\sum_{d\mid x}f(d)g\left(\tfrac{x}{d}\right)=\sum_{ab=x}f(a)g(b)狄利克雷卷积的计算过程可以简单表示为 $h=f\ast g$ 然后我们就可以有如下狄利克雷卷积的性质 ...
【算法介绍】原根与离散对数
文章总览：春风得意原根与离散对数，是非常玄学的概念（虽然说只是高联初等数论，但是本蒟蒻已经不会了），由于关于原根和阶的一些性质，我在搜索的过程中遇到了一个叫做群论的东西，这玩意对于我来说略有超纲有缘再见罢。这篇文章的内容限定于下。
阶的定义性质及其证明
原根的定义性质及其证明
原根的出现情况
如何求原根
指标的定义及其性质
互素情况下的指标计算（BSGS，Baby-Step Giant-Step）
非互素情况下的指标计算（拓展 BSGS）
参考资料
前置知识：时运驰骋
阶的定义性质及其证明
阶的定义
阶的性质及其证明
阶的定义首先要知道原根，就需要一个非常重要的前置知识，没有它甚至连原根都算不出来，他就是阶。首先给出阶在数学上的定义。我们定义满足 $a^r\equiv 1\pmod p$ 其中 $\gcd(a,p)=1\ (p\gt 1)$ 的最小正整数 $r$ 是 $a$ 对模 $p$ 的阶，记作 $\delta_p(a)$ 。
定义非常好理解，但是始终是抽象的，我们可以大概的举几个例子。比如说下面的例子中我们都取 $p=7$：
当 $a = 2$ 时，我们可以枚举：
$ ...