数论

整除 若 \(a / b (b \ne 0)\) 为整数，则称 \(b\) 整除 \(a\) ，记作 \(b \mid a\) 。若 \(a / b\) 和 \(c / b\) 的余数相等，则称 \(a, c\) 模 \(b\) 同余。 同余 关于同余，有以下命题等价： \(a\) 和 \(b\) ......

一、应用情景 求 \(\sum\limits_{i = 1}^{n} g(i)\lfloor\frac n i\rfloor,n\leq 10 ^{12}\) 二、常见结合 莫比乌斯反演 …… 三、算法原理&代码实现 实际上，\(~\lfloor \frac n i\rfloor~\)的取值其实最多 ......

目录 前言 数论基础 1.1 整除 1.2 带余除法，同余 质数 2.1 唯一分解定理 2.2 质数筛（线性筛） 2.3 欧拉函数 最大公因数/最小公倍数 3.1 辗转相除法 3.2 裴蜀定理 3.2 扩展欧几里得算法 线性同余方程 4.1 费马小定理 4.2 欧拉定理 4.3 逆元 4.4 求解线 ......

0 前言 闲的没事的时候可能会摸鱼写一写，都是些非常基础的东西。 最高大概会写到 exCRT 和 exBSGS 吧，阶和原根往后的我也不会了，但是前面的内容会时不时来补充。 为了方便偷懒，许多定理不会给出证明。 1 基本概念 \(\gcd(a,b)\) 或者 \((a,b)\)：\(a,b\) 的最 ......

数论分块 在P2424偶然学到了这个算法，觉得很有意思，于是单拎出来再学习一下。 数论分块，又叫整数分块，解决 f(n) = \sum_{i=1}^{n}g(i) \times \lfloor \frac{n}{i} \rfloor 一类问题。观察发现 \lfloor \frac{n}{i} \rf ......

Base Sieve base Dirichlet Convolution Sqrt Decomposition 会挖坑，好让复习的时候长脑子。 以下所有 \(p\) 都是质数，即 \(p\in\mathbb{P}\)，同时默认均为正整数。 Base 唯一分解定理（算术基本定理）： \[\begin ......

筛法 当我们需要获取一个区间内的所有素数的时候，我们肯定会想到筛法。 比较常见的是埃氏筛和线性筛。 他们的实现难度不高，但核心思想有所不同。 埃氏筛 考虑一个 $p \in \mathbb{P}$ 和任意一个一个大于 $2$ 的正整数 $x$，$\forall y = xp, y \notin \m ......

Codeforces Round 891 (Div. 3) F. Sum and Product 思路：对于x,y：ai+aj=x —> aj=x-ai 因此 ai*(x-ai) = y ——> ai = (x 土 sqr( x^2 - 4y ) ) /2 对应的 ai 就是要的两个值 若两个值不同 ......

扩展欧几里得 1.扩展欧几里得 用于求解\(ax + by = gcd(a,b)\)的解，利用辗转相除法构造出x，y的通解 当\(b = 0\)时，\(ax + by = a\)，可令\(x = 1，y = 0\) 当\(b \neq 0\)时，因 $gcd(a, b)$ $=$ gcd(b,a % ......

Infinite Precision: (0)数是什么？以有限的数元，度量与表示无限的现象、事物与状态，作为整个数学科学理论的根基。 以Binary二进制为例, 有{0,1}, Constant/Dynamic系统建模上，两种state(状态)？0->1与1->0代表“change变化”？ 而Dec ......

（不全，会一种就更一种...） \(1、Cayley-Hamilton\) 定理 **\(Cayley-Hamilton\) 定理： ** 设 \(A\) 是环 \(R\) 上的 \(n \times n\) 矩阵，记 \(f(\lambda) = \det(\lambda I - A)\) 为其特 ......

数论——集合符号大全 \(\mathbb N\)：自然数集合 \(\{0, 1, 2, 3, \dots\}\) \(\mathbb N^*\) 或 \(\mathbb N^+\)：正整数集合 \(\{1, 2, 3, \dots\}\) \(\mathbb Z\)：整数集合 \(\{\dots, ......

数论——欧拉函数、欧拉定理、费马小定理 欧拉函数 定义 欧拉函数（Euler's totient function），记为 \(\varphi(n)\)，表示 \(1 \sim n\) 中与 \(n\) 互质的数的个数。 也可以表示为：\(\varphi(n) = \sum\limits_{i = ......

数论——欧拉函数、欧拉定理 欧拉函数 定义 欧拉函数（Euler's totient function），记为 \(\varphi(n)\)，表示 \(1 \sim n\) 中与 \(n\) 互质的数的个数。 也可以表示为：\(\varphi(n) = \sum\limits_{i = 1}^n [ ......

数论——线性同余方程、乘法逆元 众所周知： 说明 除非特殊说明，以下提到的 exgcd 函数均定义为： // ax + by = gcd(a, b) ll exgcd(ll a, ll b, ll &x, ll &y, ll d = 0) { if (b == 0) x = 1, y = 0, d ......

回顾:FFT FFT（快速傅立叶变换）学习 - Isakovsky - 博客园 (cnblogs.com) 目的:将多项式的系数表示法形式转换为点值表示法形式,或者说,快速计算出多项式在若干个点上的值. 中心思想:适当地选取自变量,使得自变量两两互为相反数,求出的多项式值可重复利用,减少运算次数 例 ......

数论——欧几里得算法和扩展欧几里得算法 引入 最大公约数 最大公约数即为 Greatest Common Divisor，常缩写为 gcd。 一组整数的公约数，是指同时是这组数中每一个数的约数的数。\(\pm 1\) 是任意一组整数的公约数； 一组整数的最大公约数，是指所有公约数里面最大的一个。 最 ......

在系数均为整数的时候，可以用NTT代替FFT，这样不会出现精度问题。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 20000005; const lld g = 3, mod = ......

快速幂 定义 快速幂，是一个在 \(\Theta(\log n)\) 的时间内计算 \(a^n\) 的小技巧，而暴力的计算需要 \(\Theta(n)\) 的时间。 解释 \[\because a^{b+c}=a^{b} \times a^{c},a^{2b}=a^{b}\times a^{b}=( ......

tax 题目： 小码哥要交税，交的税钱是收入 \(n\) 的最大因子（该最大因子为不等于 \(n\) 的最大因子），但是现在小码哥为了避税，把钱拆成几份（每份至少为 \(2\)），使交税最少，输出税钱。 格式： 输入格式：一个正整数 \(n\) 表示所以的钱数。 输出格式：输出一个正整数，表示税钱。 ......

写在开头：word的公式打不上来，只能截图了 一.组合数学 (1) 加法定理与乘法原理 加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法。那么完成这件事共有N＝m1＋m2＋…＋mn种不同的方法。 乘 ......

引入 有 \(n\) 个元素进栈序列为 \(1,2,3,4\dots n\)。求有多少种出栈序列 我们需要确保最后一次操作后，栈中没有元素。因此，共有 \(2n\) 次操作。（每个元素进栈一次，出栈一次） 对于每次操作，如果我们想出栈，则它一定要有数字可以 pop。如果我们把栈抽象成一条链，若第 \ ......

# 数论杂谈 记录一些小小的东西 ## 贝尔数（bell） $Bell(n)$ （$B_n$）表示有 $n$ 个元素的集合划分成若干个互不相交的子集的方案数 $$B_0=1,B_1=1,B_2=2,B_3=5,\dots$$ $$B_0=1,B_{n+1}=\sum_{i=0}^n C_n^i\ti ......

`2023-07-29 16:22:14` # 辗转相除法 (求gcd) 求 $a,b$ 的最大公约数。 假设 $a\ge b$ ，令 $gcd(a,b)=d$（下文都这样表示）。 那么设 $a=k_1d$,$b=k_2d$，则 $a\mod b =(k_1-rk_2)d$，当 $k1-rk2>0$ ......

# 莫比乌斯反演 ## 定义 先讲讲莫比乌斯函数的定义： $\mu(x) =\begin{cases} 1 &n=1 \\ 0 &n含有平方因子 \\ (-1)^k &k为n的本质不同质因子个数 \end{cases}$ 我们对 $n$ 进行质因数分解， $n= \prod_{i=1}^k p_i^ ......

# 一、质数 ### 1.质数的定义： 如果一个正整数无法被除了1和它本身以外的任何自然数整除，那么这个数是质数。否则，这个数是合数。 需要注意的是，1既不是质数也不是合数。 ### 2.埃筛： 2.埃筛： 问题：给定一个正整数 $n$ ，找到$1\sim n$中的所有质数。 思路：我们可以从 $2 ......

对于任意奇质数 $p$，对于任意整数 $k < p-1$，有 $ p|\sum_{i=1}^{p-1}i^k$ 证明： 取 $p$ 的原根 $g$，由简化剩余系的性质知： 在 $\mod p$ 意义下，有 $$ \{g, 2g,\cdots, (p-1)g\} = \{1, 2, \cdots, p ......

# 数论 ### 模运算 > $a\%b = a-b*floor(\frac ab)$ 费马小定理 $a^{p-1} \% p=1$ ### 最小公倍数&最大公约数 (a,b)表示最大公约数 [a,b]表示最小公倍数 $(a,b)*[a,b] = ab$ 辗转相除 ```c if (a % b==0 ......

题意：很简单，给你l，r，让你输出对于这个区间中任意两个不同的数字的gcd组成的set的大小是多大。至于题面，我只能说，聪明人早就看出来那些图啊边啊啥的都是唬人的。 做法：显然我们是要去枚举的，但是我们不能去枚举选的那两个数字。所以我们选择枚举gcd有哪些。这些gcd又分两种： 第一种，假如一个数字 ......

**题目大意：** *** ```cpp #include using namespace std; typedef long long ll; const ll mod=1e9+7; ll n; ll lcm(ll x,ll y){ return x/__gcd(x,y)*y; } int mai ......