【奇技淫巧】欧拉函数与欧拉定理
文章总览:坠临万界的星芒欧拉函数和欧拉定理也是非常基础的数论知识。欧拉函数做为积性函数,并且自身携带欧拉名称加持各种优良性质,被广泛的运用到各个数学推导方面;而欧拉定理更是必不可少,计算逆元是它最基本的运用,它也是凌驾于费马小定理的存在(费马小定理可以从欧拉定理中得出);并且其拓展即拓展欧拉函数还可以在取模运算中缩小大指数范围,等等等等。接下来我们介绍无所不能的——欧拉函数与欧拉定理。
欧拉函数推导
欧拉函数性质
欧拉函数的计算
欧拉函数拓展
欧拉定理推导
拓展欧拉定理推导
概念基础:因缘假合的人身
欧拉函数推导
欧拉函数性质
欧拉函数基础推导关于欧拉函数,就从最基础的开始讲起。我们定义函数 $\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$ 时,我们可以枚举:
$ ...