数论

- ### 数论 - #### 质数 - 在大于1的整数中，只包含1和本身这两个约数，就被称为质数，也叫素数 - ##### 质数的判定 - ###### 试除法 - 遍历2-n，若有约数则不为质数 O(n) - 优化： - d整除n，则n/d也整除n，约数总是成对出现，只要找较小的约数，即取d 2 ......

## 前言： 可以会乱记一些技巧吧。 ### 交换求和顺序 如果不确定可以将条件写成 [A] 的形式，交换完求和顺序再把这个条件放里面。 例如： $$ \sum_{i=1}^n \sum_{d} [d | i] = \sum_{d=1}^n \sum_{i} [d|i] = \sum_{d=1}^n ......

###### @Coding: Typora+LaTeX ###### @Author : [DorinXL](https://dorinxl.gitee.io/)（[博客](https://www.cnblogs.com/DorinXL/)） ###### @Time : 2023/8/4 ## ......

## [P1390公约数的和](https://www.luogu.com.cn/problem/P1390) 简单莫反题。要求 $$ \sum_{i=1}^{n}\sum_{j=i+1}^ngcd(i,j) $$ 可以先考虑问题的简化版： $$ \sum_{i=1}^{n}\sum_{j=1}^n ......

# 解析数论之原根 ## 目录 - Chapter1 什么是整数的次数，什么是原根 - Chapter2 谁有原根？ ## Chapter1 什么是整数的次数，什么是原根 - **Definition**： 对于$(a,m)=1,m\ge1$，考虑所有$a,a^2,a^3,\cdots$，我们通过欧 ......

#### GCD & exGCD 首先我们考虑辗转相除法的过程，因为 $(a,b)=(b \bmod a,a)(0<a<b)$，$(0,b)=b$，所以我们就可以每次将 $b$ 转化为严格更小的 $b$ 的问题。归纳则得到答案。 现在我们考虑扩欧的过程，我们需要对 $ax+by=1$ 找到一组解。那 ......

# 8.1 数论进阶（数论函数相关） 以下记 $F$ 为 $f$ 的前缀和。$n/m$ 表示 $\left\lfloor\frac{n}{m}\right\rfloor$。 ## 整除分块 1. $n/i$ 取值只有 $O(\sqrt{n})$ 种。 2. $a/(bc)=(a/b)/c$。 3. ......

## 理论基础 ### 中国剩余定理及拓展 > 已知 $x \equiv a_i (\bmod p_i\ )$，求 $x \bmod \operatorname{lcm}\{p_i\}$ 的值。 - 若 $p_i$ 互质，那么我们只需要计算 $c_i$ 使得 $$ \prod\limits_{j \ ......

# 逆元 若 $ax=1\pmod p$，那么称 $a$ 是 $x$ 的逆元，显然 $x$ 也是 $a$ 的逆元。 两边同时除以 $a$ 得到 $x=\frac1a\pmod p$，可以写成 $x=a^{-1}\pmod p$，这么看来，乘法逆元就是取模意义下的倒数啊。 若 $p$ 为质数，$0$ ......

### 1. 桌球问题 ```txt 矩形球桌四个角有洞 yx 坐标在 (0, 0) (m, 0) (m, n) (0, n) 球从 (0,0) 沿 45 度方向无限大力发射，求mn满足啥条件能落袋 解法: 这种桌球问题只要无限延伸方块就行，相当于解 y=x 有没有 (am, bn) 解，其中 a ......

# 数学知识 - 平面直角坐标系 - 二次方程与二次函数 - 简记符号：$\sum$ $\prod$ $⌊n⌋$ 连加 连乘 向下取整 - 等差数列求首项、求末项、求和公式 - 等比数列首项为 $a$，公比为 $q$，项数为 $n$，求和 - 等比数列：$S=a+aq+aq^2+...+aq^{n- ......

# 7.29 数论 WIP $a\equiv b\pmod p\Rightarrow \frac{a}{d}\equiv \frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)$。 ## exGCD 1. 若 $(a,b)=1$，则 $0\leq xb\to a\bm ......

## 前言 [更熟悉的阅读体验?](https://www.luogu.com.cn/blog/defineXD114514/chu-deng-shuo-lun-xue-xi-bi-ji) 前置知识（这个应该很显然）：$\operatorname{lcm}(a,b)=\dfrac{ab}{\gcd( ......

## AT_abc182_d 题解 [洛谷链接](https://www.luogu.com.cn/problem/AT_abc182_d)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/abc182_d) 本篇题 ......

## 前言 一直不是很会生成函数，但是平常遇到的数论题，很多地方都是会用到生成函数，现在正好有了时间可以搞一搞 未来说不定会补上 NTT。 ## FFT （下文极有可能有一些加一减一的不合理的地方，可能以后会修修） 如果不会 FFT 那么生成函数肯定就完全做不了题了。（写过一篇不过当时根本不理解，胡 ......

## A. 循环与非 **题目描述** 给定长度为 $n$ 的序列 {$a_n$}，每一个数字都不超过 $2$ 的 $k$ 次方。给定 $m$ 次操作，每次操作形如： `0 x y` ：将 $a[x]$ 改为 $y$。 `1 x y` ：令 $t=y$ NAND $a[0]$ NAND $a[1]$ ......

[$$\text{建议阅读}$$](https://www.cnblogs.com/So-noSlack/p/17569390.html) ## A. 优美子数列 **题目描述** 数学家小 $Q$ 得到了一个长度为 $n$ 的数列 {$a_n$}。 小 $Q$ 的幸运数字是 $k$，所以他认为，若 ......

> ###### @Coding: Typora+LaTeX > > ###### @Author : [DorinXL](https://dorinxl.gitee.io/)（[博客](https://www.cnblogs.com/DorinXL/)） > > ###### @Time : 20 ......

Upd on 2023.1.12 **添加了整除分块和莫比乌斯反演。** Upd on 2023.7.22 **重新排版，添加、删去了一些内容，修改了一些晦涩难懂的描述，开放阅读。** ### $$\huge\textbf{0x01}\ \large\textbf{数论入门}$$ > "质数是指在大 ......

> ###### @Coding: Typora+LaTeX > > ###### @Author : [DorinXL](https://dorinxl.gitee.io/)（[博客](https://www.cnblogs.com/DorinXL/)） > > ###### @Time : 20 ......

# 狄利克雷卷积 ## 定义 两个数论函数 $f,g$ 的狄利克雷卷积被定义为 $$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$ 简记作 $h=f*g$，另一个常用的等价形式是： $$(f*g)(n)=\sum_{xy=n}f(x)g(y)$$ ## 性质与结论 狄利克雷卷 ......

### exgcd 点击查看代码 ``` __int128 exgcd(__int128 as,__int128 bs,__int128 &x,__int128 &y){ if(bs==0){ x=1; y=0; return as; } __int128 ans=exgcd(bs,as%bs,y, ......

## 中国剩余定理 ### 内容 考虑形如下列形式的方程组： $$\begin{cases}x\equiv a_1\pmod {m_1}\\x\equiv a_2\pmod {m_2}\\...\\x\equiv a_n\pmod {m_n}\end{cases}$$ 当 $m_1,m_2,\dot ......

## 欧拉函数 ### 定义与性质 一个数的欧拉函数被定义为**小于等于**$^{①}$该数的与该数互质的数的个数，记作 $\varphi(n)$，这是一个积性函数$^②$。 ### 计算 根据定义，可以得出 $\varphi(n)$ 的计算式： $$\varphi(n)=\sum_{i=1}^n[ ......

## 概念 我们考虑这样一个问题：求 $\sum_{i=1}^{k} \lfloor \dfrac{n}{i} \rfloor$ 我们以 $n=7,k=7$ 为例子，先画出 $f(x) = \dfrac{7}{x} \ (1 \leq x \leq 7)$ 的图像 ![](https://pic.i ......

# 数论 被薄纱了/kk 授课老师：南京大学-朱富海教授 ### 20230710 #### 裴蜀定理 对于给定不全为零的整数的 $a,b$ 一定存在一对整数 $x,y$ 满足 $ax+by=gcd(a,b)$ 。 ##### 证明： 1. $a==0$ $or$ $b==0$ 显然成立； 1. 设 ......

# 数论专题练习 ## [A - Beautiful Numbers](https://vjudge.csgrandeur.cn/contest/542598#problem/A) ### 题意：输入a，b，n，求只包含a，b的n位数并且n位之和为a或b的数量 * 枚举a和b的数量，判断它们的和是否 ......

# 数论 ## 最大公约数 ( $gcd(a,b)$ ) * 由欧几里得定理可知gcd(*b*,*a* mod *b*) ```c++ ll gcd(ll a,ll b) { if(b == 0) return a; else return gcd(b,a%b); } ``` * 顺便得出两数的最小 ......

整除分块是为了解决一个整除的求和的问题：sum(floor(n/i))(1<=i<=n) ，如果直接暴力计算复杂度O（n），但整除分块的复杂度为O（2sqrt(n)），其中的2为常数，可以忽略，那么复杂度为O(sqrt(n)) 下面给出整除分块的模板代码 #include<bits/stdc++.h ......

# [初等数论]欧几里得算法：最大公因数/公因式求解算法的数学证明与程序实现 对广大数学或计算机爱好者来说，找两个数的公因数向来是绕不过去的问题．本文将带大家用小学二年级的知识推出上述问题的最优算法：欧几里得算法，并展示其程序实现．以下是本文索引： 1. 欧几里得算法 1. 简洁的定义 2. 快速的 ......