数论ntt

数论中一个有趣的小结论

对于任意奇质数 $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 ......
数论 结论

FFT & NTT 学习笔记

## FFT FFT 是一种高效实现 DFT 和 IDFT 的方式,可以在 $O(n \log n)$ 的时间内求多项式的乘法。 ### 多项式的点值表示 不同于用每项的系数来表示一个多项式,我们知道对于给定的 $n+1$ 个点值,可以确定唯一的 $n$ 次多项式。这种用点值表示多项式的方法叫点值表 ......
笔记 FFT amp NTT

数论

# 数论 ### 模运算 > $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 ......
数论

E. Josuke and Complete Graph 数论分块

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

【CF1542C】Strange Function(数论)

**题目大意:** *** ```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 ......
数论 Function Strange 1542C 1542

【提高级】数论

# 前言 前段时间在补提高大纲,补完之后这篇博客用来记录梳理复盘提高大纲里数论的一些知识点,有错误欢迎批判捏。 # 欧拉函数 ## 定义 $\varphi(n)$ 表示小于等于 $n$ 中与 $n$ 互质的数的个数,即 $\varphi(n)= \sum ^n _{d=1} [\gcd(d,n)=1 ......
数论

【1342C】Yet Another Counting Problem(数论)

**题目大意:** 求有多少$x(1\le l\le x\le r\le 10^{18})$满足$(x\mod a)\mod b\neq(x\mod b)\mod a(1\le a,b\le 200)$,有$q(1\le q\le 500)$次询问。 *** 设答案为$f(l,r)$,考虑前缀和$f ......
数论 Counting Another Problem 1342C

【1165D】Almost All Divisors(数论)

**题目大意:** 给出一个数的所有因数(除了$1$和这个数本身),判断这个数是否存在。 *** 先将所有因数排序,然后计算最小因数和最大因数的积,我们设这个数为$x$。 如果$x$满足了以下的任意一个条件,则答案为不存在: 1. 存在一个$k$,第$k$大的数和第$k$小的数之积不等于$x$。 2 ......
数论 Divisors Almost 1165D 1165

基础数论

质数: 在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数 合数:在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数 约数(因数) :能够将一个数整除的数 质因数:能够将一个数整除的质数 互质:公约数只有1的两个整数 ## 质数 质数:在大于1的整数中,如果只包含1和本 ......
数论 基础

『学习笔记』整除分块(数论分块)

## 简述 整除分块这个东西听起来不是很抽象,但是我理解起来的确有点抽象(可能因为我太菜了吧)。那就先放张图: ![image](https://img2023.cnblogs.com/blog/2680753/202308/2680753-20230826212344938-943289322.p ......
数论 笔记

NC53079 Forsaken喜欢数论

[题目链接](https://ac.nowcoder.com/acm/problem/53079) # 题目 **题目描述** ​ Forsaken有一个有趣的数论函数。对于任意一个数 $x$ , $f(x)$ 会返回 $x$ 的最小质因子。如果这个数没有最小质因子,那么就返回0。 ​ 现在给定任意 ......
数论 Forsaken 53079 NC

数论-同余与扩展欧几里得详解(附例题及代码)

#数论-同余与扩展欧几里得详解(附例题及代码) 注意:这篇文章的信息量会有一点多,请耐心看完 ##一.同余 ###1.1 同余的定义 给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m) 简单来说,对于x,y ......
数论 例题 代码

【学习笔记】简单数论-高斯消元与线性空间

## 友情提示 - 本博客内部分内容因缺乏样例,可能晦涩难懂,建议参考蓝书或者[数论小白都能看懂的线性方程组及其解法](https://www.luogu.com.cn/blog/ShineEternal/linear-equation-group)。 ## 线性方程组 - 线性方程组是由 $M$ ......
数论 线性 笔记 空间

数论笔祭 - 林学长的第二数学

# 林学长讲课笔记 ## 极限 $\lim_{x \to x_0} f(x)$ 考虑运算法则: - 一般来说,函数的和差商积的极限等于函数的极限的和差商积。 但是例外: $$ \lim_{x \to 3} \frac {x - 3}{x^2 - 9} $$ 考虑极限约去 $x - 3$ 得到: $$ ......
数论 学长 数学

NTT 小记

[TOC] 数论来力……证明之类的也许会大挂。 或者其实还好,在参考别人的证明思路之后。 ### Pre 注意到 FFT 中需要复数计算,原因在于涉及到了单位复数根。 有没有替代品?复数域(这是包含实数和虚数的)内暂时没有。 不过我们可以考虑在模意义下找一个。 ### 阶与原根 对于一个正整数 $n ......
小记 NTT

【学习笔记】简单数论-同余

- 同余 - 若整数 $a$ 和整数 $b$ 除以正整数 $m$ 的余数相等,则称 $a,b$ 模 $m$ 同余,记为 $a \equiv b \pmod{p}$ 。 - 性质 - 自反性: $a \equiv a \pmod{p}$ - 对称性:若 $a \equiv b \pmod{p}$ ,则 ......
数论 笔记

【学习笔记】简单数论-质数

- 质数的个数是无限的。 - 试除法:若一个正整数 $N$ 为合数,则存在一个能整除 $N$ 的数 $T$ ,其中 $2 \le T \le \sqrt{N}$ 。 - 时间复杂度为 $O(\sqrt{N})$ 。 - 代码实现 ```cpp bool isprime(int n) { if (n ......
质数 数论 笔记

【学习笔记】简单数论-快速幂

[luogu P1226 【模板】快速幂 | 取余运算](https://www.luogu.com.cn/problem/P1226) ```cpp #include using namespace std; #define ll long long #define sort stable_sor ......
数论 笔记

【学习笔记】简单数论-最大公约数

- 一个整数 $N$ 的约数上界为 $2\sqrt{N}$ 。 - $1 \sim N$ 每个数的约数个数的总和大约为 $N \times logN$ 。 - 取模运算性质 - $(a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p$ ,反之亦成立。 - $(a ......
最大公约数 公约数 数论 笔记

数论基本算法学习笔记

# 数论基本知识 ## 裴蜀定理 不定方程$a\cdot x+b\cdot y=c$有解当且仅当$c$是$\operatorname{gcd}(a,b)$的倍数。 **证明**: $$ \begin{aligned} &设集合S=\left\{ \left\vert \mu\cdot a+\nu\c ......
数论 算法 笔记

数论学习笔记

# 逻辑 ### 1. 充分条件、必要条件与充要条件的概念 若 $p\Rightarrow q$,则 $p$ 是 $q$ 的充分条件,$q$ 是 $p$ 的必要条件。 $p$ 是 $q$ 的充分不必要条件,$p\Rightarrow q$ 且 $q\not\Rightarrow p$。 $p$ 是 ......
数论 笔记

「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$ ,反之亦成立。 ......
数论 笔记