数论

## 线性筛素数 直接上代码。 ```cpp const int MAXN=100000008; bool np[MAXN]; vector prm,pre; void gg(const int N=100000000){ pre.resize(N+1); for(int i=2;i 积性：如果对于 ......

# 排列组合 > 排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。 OI Wiki ### 乘法原理和加法原理 加法原理，就好比一个工作，有 $n$ 个解决的方案，第 $i$ 项方案有 $a_{i}$ 种不同的实现方式，所以这个 ......

# 题目地址 https://ac.nowcoder.com/acm/contest/57677/A # 代码 ``` use std::io::{self, BufRead, Write}; fn is_prime_triival(n: i128) -> bool { if n i128 { le ......

# 前言 在学习本节内容前，最好先学习[同余的基本性质](https://www.luogu.com.cn/blog/157884/tong-yu-di-ji-ben-xing-zhi)以加深理解。 # 一堆定理 * 定理1： **若** $$a,b,m,n \in \mathbb Z,c \mid ......

# 前言 在学习本节内容前，请确保已完成了[同余方程](https://www.luogu.com.cn/blog/157884/basic-math-note-2)的学习。 # 模的逆 ## 引入 很多题目都会要求我们对答案取模。 如果运算中只有加法、乘法当然没问题。 但是如果有除法就完蛋了。 所 ......

# 前言 在学习本节内容前，请确保已完成了[二元不定方程](https://www.luogu.com.cn/blog/157884/basic-math-note)的学习。 # 同余方程 ## 有无解的判别 对于一个方程形如： $$ax \equiv b \pmod m$$ 其中 $$a,b \i ......

整除 设 $a,b\in \mathbb{Z},a\ne 0$。如果 $\exists q\in \mathbb{Z}$，使得 $b=a\times q$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$ ；$b$ 不被 $a$ 整除记作 $a\nmid b$ 。 OI Wiki 整除 ......

AtCoder abc230_e AtCoder abc230_e Fraction Floor Sum 求: $$\sum_{i = 1}^N ⌊\dfrac{N}{i}⌋$$ P2261 [CQOI2007]余数求和 P2261 [CQOI2007]余数求和 $$G(n, k) = \sum_{ ......

最近打算学计数DP，然而我数学基础太弱，故记此文。（问了一下，这东西只不过是小学奥数而已，我好蒻） 公式 加法原理：$ S= \sum_{i=1}^n a[i] $ 乘法原理：$ S= \prod_{i=1}^n a[i] $ 二项式定理：$(a+b)^n = \sum_{i=0}^n a^{n-i ......

欧拉函数 定义 $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 ......

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

莫反，欧拉反演 常用结论： $\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 ......

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

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= ......

预备 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) ......