数论 结论

欧拉函数 定义 $1-N$中与 $N$ 互质的个数被称为欧拉函数，记为 $φ(n)$。 公式 设 $n={p_1}^{c_1}{p_2}^{c_2}\cdots*{p_m}^{c_m}$ 则 $φ(n)=n*\dfrac{p_1-1}{p_1}\dfrac{p_2-1}{p_2}\cdots*\df ......

一道需要一些猜结论技巧的中档题。 首先突破口在于排列长度恰好等于不是额外输入的某个数 $k$ 而是 LDS 与 LIS 的乘积，这显然启示我们去找一些性质。根据 dilworth 定理，最长反链等于最小链覆盖，故 LIS 的长度，就是最少需要的递减数列的个数使得每个元素被覆盖至少一次，而每个递减数列 ......

整除的概念和性质： 素数和合数的定义： 例题一： ......

莫反，欧拉反演 常用结论： $\mu1=\epsilon,\varphi1=id$． $\mu^2(n)=\sum_{d^2|n}\mu(d)$． $d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$． $\varphi(xy)=\frac{\varphi(x)\varp ......

质数 在大于1的整数中, 如果只包含1和本身这两个约数, 就被称为质数, 或者叫质数 (1)质数的判定——试除法 //试除法判定质数模板 bool is_prime(int x) { if(x<2)return false; for(int i=2;i<=x/i;i++) if(x%i==0)ret ......

例题一： 例题二： 例题三： 例题四： ......

题目描述 一个长度为 $n$ 的数组$A$，每秒都会变成一个长度为 $n − 1$ 新数组 $A'$，其变化规 则如下： 若当前数组 $A$ 的长度 $n$ 为偶数，则对于新数组 $A'$ 的每一个位置 $i(1 ≤ i < n)$来说，$A'[i]=A[i]+A[i+1]$ 若当前数组 $A$ 的 ......

0. 前置知识与基本定义 $[op]$：值为 $1$ 当且仅当方括号内条件为真。记为艾弗森括号 唯一分解定理：一个正整数 $x$ 可以被唯一分解为 $\prod\limits_{i=1}^m p_i^{c_i}$，其中 $\forall i\in[1,m],p_i\in \mathbb{P}$。（关 ......

数论基础 基本概念： 模：$a\bmod p$ 即 $a\div p$ 的余数 整除：$a\mid b$ 即 $b\bmod a=0$ ，同时称 $a$ 是 $b$ 的因数（约数） 质数：有且只有两个约数的数（ $1$ 不是质数，因为它只有一个约数） 质因数分解：将一个正整数 $n$ 分解为 $n= ......

挺有意思的结论题，结论的证明比较复杂。据出题人说他大概想了几天几夜才证出来，所以本篇题解并不详细给出结论证明，如果有兴趣可以自己去看出题人的题解：https://www.luogu.com.cn/blog/AlexWei/solution-p8456。 首先涉及到简单路径，肯定往双连通分量的方向思考 ......

预备 0.1 渐进符号 其实不少高等数学 / 数学分析教材在讲解无穷小的比较时已经相当严谨地介绍过大 O、小 O 记号，然而各种历史习惯记法的符号滥用（abuse of notation）[1] 直到现在都让笔者头疼. These notations seem to be innocent, but ......

最大乘积 题目描述 一个正整数一般可以分为几个互不相同的自然数的和，如 $3=1+2$，$4=1+3$，$5＝1+4=2+3$，$6=1+5＝2+4$。 现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。 输入格式 只一个正整数 $n$，（$3 \le ......

SageMath是一个覆盖许多数学功能的应用软件，包括代数、组合数学、图论、计算数学、数论、微积分和统计。 安装sagemath（ubuntu） sudo apt install sagemath 在命令行输入sage启动sagemath 输入tutorial或manual()打开离线文档 素数测试 ......

同余 定义不多说了，$a\equiv b\pmod m$。 性质 若 $a\equiv b,c\equiv d$，则： $a+c\equiv b+d$ $a-c\equiv b-d$ $a\cdot c\equiv b\cdot d$ 常用的等价形式为，取模运算关于加法和乘法可以拆分运算。 线性同余 ......

参考：https://www.cnblogs.com/alex-wei/p/Number_Theory.html ......

高精度 高精度加法 vector<int> add(vector<int> &a, vector<int> &b) { vector<int> c; int t = 0; // 代表进位 for (int i = 0; i < a.size() || i < b.size(); ++i) { if ......

https://codeforces.com/contest/1433/problem/E 题目大意： n个人(n是偶数)跳了两轮舞，每轮舞正好有n/2个人。你的任务是找出n个人跳两轮舞的方法，如果每轮舞正好由n/2个人组成。每个人都应该属于这两种圆舞中的一种。 人相同位置不同也算是同一种方案。 i ......

@(数论板块笔记上blog) 1.exgcd 函数代码： long long exgcd(long long a,long long b,long long&x,long long &y){ if(b==0){ x=1,y=0; return a; } long long d=exgcd(b,a%b ......

剩余类与完全剩余系 剩余类 定义： $C_r$:形如$qm+r$的所有整数组成的集合 $C_0,C_1,...,C_(m-1)$:模数$m$的剩余类 完全剩余系 定义： 1.从剩余类的每类中各取一个数，组成的$m$个数称为模数$m$的一组完全剩余系。 证明……是一组完全剩余系/通过完全剩余系：两两对 ......

DAY10共2题： 月月给华华出题 华华给月月出题 难度较大。 🎈 作者：Eriktse 🎈 简介：211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀 🎈 原文链接（阅读原文获得更好阅读体验）： ......

在做数论题时，往往需要进行和式变换，然后变换成我们可以处理的和式，再针对和式做筛法、整除分块等操作。 本文将介绍一些常见的和式变换技术。 以下出现的概念大部分为个人总结，未必是学术界/竞赛界的统一说法，有不严谨的地方请谅解。 🎈 作者：Eriktse 🎈 简介：19岁，211计算机在读，现役AC ......

简单介绍一下数论分块的思想。空说无益，先上几道题。 题1：P1403 约数研究 链接如下：https://www.luogu.com.cn/problem/P1403 如果这道题要对每一个数进行分解、统计，未免太麻烦。我们不妨换个思路，假设这里的N是30，那么这个区间内整体的数字分布如下图： 这里我 ......

$\mathcal{0x01 绪论}$ $\mathcal{质数的判定试除法 or 六倍原理}$ 一个合数的约数总是成对出现的,如果$d|n$($d$能被$n$整除）,那么$(n/d)|n$,因此我们判断一个数是否为质数的时候, 只需要判断较小的那一个数能否整除n就行了,即只需枚举$d<=(n/d) ......

模板: //质数判定--试除法 //朴素 O(N) bool is_prime(int n) { if(n<2)return false; for(int i=2;i<n;i++) { if(n%i==0)return false; } return true; } //朴素优化 O(sqrt(N) ......

网上搜集的，怕忘了，记录一下。 摘自 $\text{OI-wiki}$，$\text{mina}$ 等各种各样乱七八遭的地方。 最小割 源点 $s$，汇点 $t$。 记对残量网络跑 $\text{tarjan}$ 得到的第 $i$ 个点所在 $\text{SCC}$ 编号为 $scc_i$ 最小割方 ......

Hensel 引理、原根 一、Hensel 引理 Hensel 引理：$\mathsf{f(x)}$ 是一个整系数多项式 $\mathsf{(\ f(x) \in Z(x)\ )}$，对于素数 p，整数 a 使得 $\mathsf{p^{k} \mid f(a)}$，$\mathsf{(\ f^{' ......

https://codeforces.com/contest/1360/problem/D ###D. Buying Shovels 题目大意： 一个人想买正好n把铲子。店内有k种包装的铲子:第i种包装正好由i把铲子组成(1≤i≤k)。这家商店有无限数量的包装。 选择一种类型的包装，然后购买几个(一 ......

费马小定理求乘法求逆元 应用条件：当模数p为质数的时候 $\because ax \equiv 1 \pmod{p}$ 由费马小定理可得：$ax \equiv a^{p-1} \pmod{p}$ $\therefore x \equiv a^{p-2} \pmod{p}$ 至此，我们可以通过快速幂的 ......

你猜为什么我数学那么差？ 1. 从欧几里得算法到扩展欧几里得算法 我们一般用欧几里得算法求最大公约数，它差不多就这样 $\gcd(m, n) = \begin{cases}n&m = 0\\gcd(n, m \bmod n) & (m \not = 0)\end{cases}$ 扩欧可以用来求这个： ......

数论 $1$ $1.$ 质数 ~~定义就不说了吧。~~ 性质 $&$ 定理 质数 $p$ 有且仅有两个质因子 $1$ 和 $p$ 。 质数有无穷个。 $[1,, n]$ 中的质数个数约为 $\dfrac{n}{\ln n}$ (此结论可用来大致估算某些数论题的数据范围)。 任何一个大于 $1$ 的整 ......