数论 结论

「Note」数论方向 - 同余相关

# 1. 扩展欧几里得算法 ## 1.1. 介绍 扩展欧几里得算法用于求 $ax+by=\gcd(a,b)$ 的一组特解(整数解)。 推导如下: 设 $\begin{cases}ax_1+by_1=\gcd(a,b)\\bx_2+(a\mod b)y_2=\gcd(b,a\mod b)\end{ca ......
数论 方向 Note

数论题目

小凯的疑惑 题面:Link 分析: 题意简述:给定两个互质的正整数$x,y$,求最大不能被表示成$ax+by$的数($a,b$满足 $0 \le a,b$ 且为整数) 不妨设$x<y$ ,答案为$ans$ 如果: $ ans \equiv mx(mod\,y) (1 \le m \le y-1)$ ......
数论 题目

[数论第四节]容斥原理/博弈论/NIM游戏

- ### 容斥原理 - $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ - $|\displaystyle \cup_{i=1}^n A_i |=\sum_{i}|A_i|-\sum_{i,j} ......
数论 博弈论 原理 NIM

数论函数合集

#### 整除分块 例题:[UVA11526 H(n)](https://www.luogu.com.cn/problem/UVA11526) 复杂度保证: $$ \forall n \in\mathbb{N_+},|\{ \left \lfloor \frac{n}{i} \right \rflo ......
数论 函数

数论函数小计

## 1.基础 ### 数论函数 + 定义: 数论函数,就是值域为整数(陪域为复数)的函数 ### 狄利克雷卷积 两个**数论函数**的**狄利克雷卷积**是一个新的函数 比如 $f(n)$,$g(n)$ 它们的卷积就是 $f * g$ 怎么卷呢? 定义: $\large{(f*g)(n)=\sum ......
数论 函数

数论练习题小结

### 1.[P1447](https://www.luogu.com.cn/problem/P1447) 题意:求 $$\sum\limits_{i=1}^n\sum\limits_{j=1}^m2\times (i,j)-1$$ 思考:原式等价于$2\sum\limits_{i=1}^n\sum ......
数论 练习题 小结

数论学习笔记

本文主要记录自己学习 OI 时用到的数论知识,内容偏进阶。 因为近期其实不太会用到多么高深的数论知识,所以很多内容是空中楼阁,是照抄 OI Wiki 而缺乏自己的理解,这些都等需要的时候慢慢补。这次写笔记主要在于建立起知识体系,知道有哪些东西要掌握。 那么开始。 ## 数论分块 基本的思想是集合 $ ......
数论 笔记

数论第一节:质数与质因数

参考博客: http://www.matrix67.com/blog/archives/234 https://www.cnblogs.com/1024th/p/11349355.html https://zhuanlan.zhihu.com/p/267884783 ## 素数的分布: ``` 10 ......
质因数 质数 数论

【学习笔记】简单数论

# 前言 开个大坑。 # 正文 ## 最大公约数 - 取模运算性质 - $(a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p$ ,反之亦成立。 - $(a-b) \bmod p=((a \bmod p)-(b \mod p)) \mod p$ ,反之亦成立。 ......
数论 笔记

LCM Sum[数论+树状数组]

Problem - E2 - Codeforces 给一个区间[L,R],询问有多少三元组(i,j,k)满足L=<i<j<k<=r且lcm(i,j,k)>=i+j+k. 正难则反。我们可以考虑它的补集。 lcm<i+j+k,然后是i+j+k<3*k 所以lcm<3k,又因为k是lcm的因数,所以lc ......
数论 数组 LCM Sum

数论分块

#数论分块学习 ##用途 快速计算含有$\lfloor{\frac{n}{i}}\rfloor$的和式($i$为变量) ##引理 ###引理1 $$ \forall a,b,c\in \mathbb{N_+},\quad \Big\lfloor \frac{a}{bc}\Big\rfloor=\bi ......
数论

数论20230809

# 定义1.1整除 $a$整除$b$记为$a|b$ $a|b$指$\exists n\in \mathbb{Z},使得b=an$ # 定义1.2 - 1.整除的传递性:$a|b,b|c\Rightarrow a|c$ - 2.整除的可加性:$n|a,n|b\Rightarrow n|a\pm b$ ......
数论 20230809

数论全家桶

# 数论全家桶 [toc] ### 欧拉定理 1.结论 $$ ∀a,m∈Z且gcd(a,m)=1,a^{\varphi(m)}\equiv1\ (mod\ m) $$ 欧拉定理的一个常见用法是对指数降幂。 应用当mod数质数时,有 $$ a^b \equiv a^{bmod\phi(m)} (mod ......
数论 全家

[数论第二节]欧拉函数/快速幂/扩展欧几里得算法

- ### 欧拉函数 - 欧拉函数$\varphi(N)$ : 1-N中与N互质的数的个数 - 若$N = p_1^{a_1} · p_2^{a_2} · p_3^{a_3} ··· ·p_n^{a_n}$ 其中p为N的所有质因子 - 则$\varphi(N) = N(1-\frac{1}{p_1} ......
数论 算法 函数

数论的一些公式

## 二项式定理 $$ (x+y)^{n}= \sum_{k=0}^{n} {n\choose k} x^{k} y^{n-k} $$ ## 二项式反演 $$ f_{n}=\sum_{i=0}^{n} {n\choose i}g_{i} \Leftrightarrow g_{n}=\sum_{i=0 ......
数论 公式

数论第一节

- ### 数论 - #### 质数 - 在大于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 ## ......
解析数论 数论 特征 有限

二分图匹配概念&结论&证明的整理总结

设 $M$ 是 $G(V,E)$ 的一个匹配 1. 先称 $M$ 中的边为匹配边,不在 $M$ 中的边为非匹配边 2. 与匹配边相关联的点,称之为配对点,不与匹配点相关联的点,称之为非配对点 3. 如果 $G$ 中的每个点都是配对点,则称 $M$ 是 $G$ 的一个**完美匹配** 4. 在 $G$ ......
amp 结论 概念

数论函数

## [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$,我们通过欧 ......
解析数论 数论

0801数论

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

【笔记】数论进阶(数论函数相关)

# 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. ......
数论 函数 笔记

20230801 数论基础学习笔记

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

通过求逆元的几种方式复习基础数论

# 逆元 若 $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- ......
数论 数学

【模板】数论基础:exGCD,exCRT,inverse,Lucas,BSGS,primitive root

# 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 ......
数论 primitive 模板 inverse 基础

初等数论学习笔记

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

第十五节 数论 - 2

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