数论ntt

### 求和符号的定义 为了简化形如 $a_1+a_2+...+a_n$ 这样求 $n$ 个数的和的表述，引入求和符号 $\sum$，将上式重表述为 $\sum\limits_{i=1}^na_i$。 其中，$i$ 被称为指标变量，取值为从 $1$ 到 $n$ 的整数，$a_i$ 为关于 $i$ 的 ......

# 1.【最大公约数（GCD）和最小公倍数（LCM）】 ## 【基本性质、定理】 * $\large gcd(a,b)=gcd(b,a−b) (a>b)$ * $\large gcd(a,b)=gcd(b,a$ $\large mod$ $b)$ * $\large gcd(a,b)$ $\larg ......

~~怎么有人选题迟了么得FFT啊。~~好久没更新博客了，来水一发！ 参考资料： NTT：https://oi-wiki.org/math/poly/ntt/ CUDA实现FFT并行计算：https://blog.csdn.net/Liadrinz/article/details/106695275 ......

## 裴蜀定理 对于任意的整数a、b，都存在一对整数x、y（注意x和y可以是负整数），使得$ax+by = gcd(a,b)$成立。或者可以这样描述：对方程$ax+by = c，(a,b,c∈Z)$，只有满足$gcd(a,b)|c$（即a和b的最大公约数可以整除c），方程才有整数解。 ## 扩展欧几 ......

## 取模 $$ (1) \quad 5 \div 3 = 1 \cdots 2\\ a = b \cdot c + d\\ (2) \quad a \div b = c \cdots d\\ b > d \ge 0\\ (3) \quad a, b, c = a / b, d = a \bmod ......

# 未完工。 目前咕掉的： 卢卡斯定理 ~~真正有用的一个没有~~ # 质数： 威尔逊定理：$p$ 为质数的充要条件为 $(p-1)!\equiv -1\pmod p$ 证明： $1.$ 充分性： 反证，假设 $p$ 是合数。 如果 $p$ 为质数的平方，例如 $p=4$，则 $3!\equiv 2 ......

# 前言 关于高次同余方程，有 $a^x \equiv b(\text{mod} \ p)$ 和 $x^a \equiv b(\text{mod} \ p)$ 两种类型，后者计算起来较为麻烦，下文就分别记述这两种高次同余方程。 # 离散对数问题 离散对数问题是在模 $p$ 意义下求解 $\log_a ......

 参考：https://www.cnblogs.com/alex-wei/p/Number_Theory.html ......

 参考：https://www.cnblogs.com/alex-wei/p/Number_Theory.html ......

## 线性筛素数 直接上代码。 ```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 ......

NTT 笔记 前言： 这个算法是与FFT 类似的，本片不会再从头讲起，建议先去补补课《FFT 笔记》。 本文只会讲一下互相关联的地方与一些不同的地方。 建议：在电脑前放好演算纸和笔。 注：本篇文章是我这个小蒟弱写的，真正的dalao请看个玩笑便好，不必争论对错（但是欢迎指出文章存在的小错误）。 NT ......

概念 多项式乘法时，我们发现暴力乘十分缓慢，但是点值乘十分快速。考虑求 $A$ 和 $B$ 的卷积。 一个 $n$ 次多项式可以被 $n+1$ 个点确定。 设多项式 $A(x)$ 的系数为 $(a_0,a_1,\cdots,a_n)$ 对其奇偶分类得 $A(x)=\sum\limits a_{2i} ......

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

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

打个广告QwQ 对应的FFT洛谷blog链接 对应的csdn博客链接 ~~个人觉得洛谷的观感最好。~~ 不忘历史 八百年前学了 $\text{FFT}$，因vicky过于垃圾，遂放弃。 七百年前重拾 $\text{FFT}$，勉强搞懂了它的递归写法，因vicky再一次懒癌附体，遂连板题都没写就弃疗了 ......

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