数论

前言 题目来源 初等数论学习I Euclid Problem：板题，用 \(exgcd\) 求出的两个解就是 \(|x|+|y|\) 最小的整数解 【模板】二元一次不定方程 (exgcd)：板题 Gift Dilemma：将方程变为 \(ax+by\equiv p-cz\)，枚举 \(c\) 前的系 ......

质数 定义 若一个正整数无法被除了 \(1\) 和它自身之外的任何自然数整除，那么称这个这个正整数为质数，否则称该正整数为合数。 在整个正整数集合中，质数的数量不多，但是无穷无尽的，分布比较稀疏，对于一个足够大的正整数 \(N\) ，不超过 \(N\) 的质数大约有 \(N / \text{In}~ ......

说在前面 默认了解一些基本定义，如整除、取模、质数等，仅有算法的思想和实现，没有且不做证明 如果需要更详细的说明、了解，也许你需要：基础数论，OI-Wiki 一些表示方法 整数：\(\mathbf{Z}\) 属于：\(a \in \mathbf{Z}\)（\(a\) 属于整数） 存在：$ \exis ......

转载 同余 定义 若 \(a,b\) 为两个整数，且它们的差能被某个自然数 \(m\) 所整除，则称 \(a\) 就模 \(m\) 来说同余于 \(b\)，或者说 \(a\) 和 \(b\) 关于模 \(m\) 同余，记为 \(a \equiv b \pmod m\)。它意味着 \(a - b = ......

加法原理、乘法原理 加法原理 应该是最简单一个了（没有之一）。 若完成一件事情有 \(n\) 类办法，\(\Large{a_i(1\leq i\leq n)}\) 代表第 \(i\) 类方法个数，那么完成这件事的方法就有 \(\Large{S=a_1+a_2+\cdots+a_n}\) ，等于 \( ......

数论结论 总结 小结论 \(1\sim n\) 的因数总共有 \(O(n\log n)\) 个，调和级数证明。 \[\varphi(ij)\varphi(\gcd(i ,j)) = \varphi(i)\varphi(j)\gcd(i, j) \]\[d(ij) = \sum_{x | i}\sum ......

为确保准确性，本文中的数默认为非负整数 欧拉好闪，拜谢欧拉 素数 基本概念 整数集合: \(2 = \{...,-2,-1, 0, 1, 2, ...\}\) 自然数集合: \(N = \{0, 1, 2, ...\}\) 整除:若 \(a=bk\), 其中 \(a,b,k\) 都是整数, 则 \( ......

快速数论变换 | NTT 初学 前置 FFT 原根 阶：称满足同余方程 \(a^x\equiv 1\mod m\) 的最小正整数解 \(x\) 为 \(a\) 的模 \(m\) 的阶，记为 \(Ord_ma\)。 观察到本质就是最短循环节，同时该同余方程类似于欧拉定理： \[a^{\varphi ( ......

C. Number Game 我们考虑那些状态是必胜态 我的回合时n为奇数（除1外），直接除以n则必胜 下面偶数的情况稍复杂 偶数我们能进行的操作只有除以一个奇数，需要考虑怎么把当前状态变为对手的必败态 偶数一定含2的因子，\(n=2^k*q,q为奇数\) 当\(k=1时如果q\)是一个质数那么只能 ......

目录质数质因数分解约数\(gcd\)求最大公约数 质数 质因数分解 算术基本定理： \(任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可以写作：\) \[N=p_1^{c_1}p_2^{c_2}...p_m^{c_m} \]\(其中c_i都是正整数，p_i都是质数，且满足p_1<p_2<.. ......

裴蜀定理 思路 不定方程 \(ax+by=c\) 成立的充要条件为 \(\gcd(a,b)|c\)。 证明： 有 \(\gcd(a,b)|ax,\gcd(a,b)|by\) \(∴\gcd(a,b)|ax+by\) \(∴\gcd(a,b)|c\) 扩展： 不定方程 \(\displaystyle\ ......

Codeforces Round 910 (Div. 2) D. Absolute Beauty 思路： 将每个 \(a_i\) 与 \(b_i\) 转化为线段，大数在后，小数在前 即 L ( min) —— R (max) 对于 \(b_i\) 和 \(b_j\) 的 交换 ： ​ L1 —— R ......

Codeforces Round 910 (Div. 2) B. Milena and Admirer 思路： 要使数组非递减，则可以先进行倒序遍历，对于当前的 \(a_i\) , 要使 \(a_i\le a_{i+1}\) 我们可以进行贪心，让 \(a_i\) 分完尽可能使每个 \(a_i / k ......

Educational Codeforces Round 139 (Rated for Div. 2) D. Lucky Chains 思路： 假设幸运为k ， 则 gcd(x+k,y+k) ≠ 1 , k取最小整数（k>=0） 由此可设 因子为 d ， (x+k)%d = 0 , (y+k)%d ......

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 就是要的两个值 若两个值不 ......

Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize 思路： 首先对 \(a\) 进行排序, 然后对所有差值取gcd ，获得可用的最大因子 \(gc\)， 答案有两种情况： 一种是 \(a_{n+1}\) ......

数论分块 求 \(\sum f(i)g(\biggl\lfloor \dfrac{n}{i} \biggr\rfloor)\)，并且 \(f(i)\) 的前缀和可以快速计算。 发现 \(\biggl\lfloor \dfrac{n}{i} \biggr\rfloor\) 的取值只有根号种，暴力做就完 ......

归不到类，说实话不知道从哪里开始。 积性函数 没啥好说。如果一个定义在 \(N+\) 集合上的函数 \(f\) 满足对于任意一对互质的正整数 \(p,q\) 都有 \(f(pq)=f(p)f(q)\)，则称 \(f\) 为积性函数。若是对于任意正整数 \(p,q\) 都有 \(f(pq)=f(p)f ......

开篇碎碎念： 在咕咕咕的接近两周时间内看了些数论，但是由于对于latex的不熟悉所以就没有整理笔记出来，总的来说就是学了下exgcd、crt。然后回老家玩了一阵子所以咕咕咕。今天啃一啃欧拉函数&欧拉定理之类的，然后就可以组合数学启动啦！ヽ(✿ﾟ▽ﾟ)ノ 欧拉函数 参考博文：Plozia的欧拉函数 定 ......

2023.12.7 cf 1907E 解题思路 首先明确，如果这三个数加起来发生了进位，那么必然不是好数（一个位换下一个位总和会有损失） 然后，结果n的每一位就可以拆成几个1，或者说几个小球，用两个隔板往小球的空隙插（注意因为0也有可能，所以小球两边也可插，可插空隙个数为num+2） 然后就可以直接 ......

前言 数论分块我实际上在2021年的暑假就已经接触过了，当时是当成了定理来记，所以现在忘得也差不多了。 最近决定重温（从零开始重修）数论分块，利用坐地铁的时间看了几篇关于数论分块的博客文章（源自《洛谷日报》），感觉有些讲得不是非常详细，质量参差不齐。有些往往只放几个性质，然后将结论直接写在下面。这种 ......

一、原根 性质 性质1 \(a,a^2,...,a^{\delta_m (a)}\)模\(m\)两两不同。 证明 反证，设存在$0 性质2 若\(a^n \equiv 1 \pmod{m}\)，则\(\delta_m (a) \mid n\)。 证明 反证，设$n=\delta_m (a)q+r，0 ......

数论 欧拉函数 定义 欧拉函数 \(\phi(n)\) 表示 \([1,n]\) 之间与 \(n\) 互质的数量。 公式 设 \(n=\alpha_{1}^{p_1} \times \alpha_{2}^{p_2} \times \alpha_{3}^{p_3} \times …… \times \ ......

同余 定义 费马小定理 定理内容：若 \(p\) 是质数，则有：$ \forall a \in Z, a ^ p \equiv a \pmod p$。 推论：当 \(\gcd(a,p) = 1\) 时，\(a ^ {p - 1} \equiv 1 \pmod p\)。 裴蜀定理及拓展欧几里德算法 裴 ......

整除 设 有整数 a,b且 a 不等于 0。 如果存在整数 q，使得 b=aq，那么就说 b 可被 a 整除，记作 a∣b，b 不被 a 整除记作 a∤b。 比如 3∣9的意思是 3能整除 9 ， 而 3∤10是3不能整除 10。 🌰 给定两个正整数a,b(0<a,b<105), 判断 a 能否整 ......

今天在群里又看到了经典的数论不等式：\(\min x, s.t. L \le ax \bmod b \le R\)。以及杜岩旭问这个是不是等价于 \(\min at \bmod b, t \in [L, R]\)。实际上当然是等价的。首先我们可以胡乱处理一下令 \(a \perp b\)，无论在哪个 ......

加法原理 若完成一件事的方法有 \(n\) 类，其中第 \(i(1 \le i \le n)\) 类方法包括 \(a_i\) 种不同的方法，且这些方法互不重合，则完成这件事共有 \(\sum\limits_{i=1}^{n}a_i\) 种不同的方法。 乘法原理 若完成一件事的步骤有 \(n\) 个， ......

#include <bits/stdc++.h> using namespace std; const int P=1e9+7; int mod(int a){//求模 return ((a%P)+P)%P; } int add(int a,int b){//加法 a=mod(a); b=mod(b ......

算法部分 杜教筛 \[S(n) = \sum_{i = 1}^{n}f(i) \]要求 \(f\)积性，且能被表示为 \(f* h = g\)，而 \(g\) 的前缀和与 \(h\) 的点值是好求的。 考虑展开狄利克雷卷积。 \[\begin{aligned} \sum_{i = 1}^{n} f* ......

#include <bits/stdc++.h> using namespace std; const int P=1e9+7; int mod(int a){//求模 return ((a%P)+P)%P; } int add(int a,int b){//加法 a=mod(a); b=mod(b ......