数论

## 算法 ### 记号 $a \mod p$：$a$ 除 $p$ 的余数，等于 $a - p \times \lfloor \frac{a}{p} \rfloor$。 $a \mid b$：$a$ 整除 $b$ 即$a$ 是 $b$ 的因数。 ### 素数判定 #### 试除法 对于任意整数 $n ......

数论基础 导读：快速幂取模、欧式筛法、裴蜀定理（贝祖定理）、威尔逊定理、费马定理、（扩展）中国剩余定理。 ### 快速幂取模 求$a^b \% p$我们有时间复杂度$O(b)$的办法。但数据规模放大时，我们的显示界面难免会出现一个老熟人 `TLE`，我们需要更**快**的方法。 根据初中数学，$a^ ......

# Order and primitive root and exponential equations(阶、原根和指数方程) ## 一、概念 ### 1、阶 阶：$a^x ≡1 (\bmod m)$上面的x就是阶 ### 2、原根 $\bmod m$的阶为$\phi(m)$的数 ### 3、指数方 ......

首先我们要明确一个方向，就是 $\text{FFT}$ 的原理是单位根的几个性质： - 消去原理： $\omega_{tn}^{tk}=\omega_{n}^k$ - 对称原理：$\omega_{n}^{k}=-\omega_n^{k+\frac n 2}$ - $\omega_{n}^k=(\o... ......

# 数论函数/莫比乌斯反演 ## 1.1积性函数 数论函数：可以认为是定义在整数上的函数。 #### 1)积性函数定义 (a,b) = 1,f(a,b) = f(a)f(b) #### 2)积性函数性质 1. **对于积性函数$f$，是被所有$p^e$处的值决定的** a = 1,f(b) = f( ......

# 初等数论 ## $\mathcal{P}art$ 1.基础概念 + 整除 对两个正整数 $a$，$b$（$b\le a$），如果存在一个整数 $k$ 使得 $a=kb$，则称 $b$ 整除 $a$，记作 $b|a$ + 带余除法 对任何整数 $a$ 和正整数 $b$，一定存在一个整数 $r\in ......

用nsqrt(n)的时间复杂度就能过 //Dreaming of Freedom:https://codeforces.com/problemset/problem/1826/C #include <bits/stdc++.h> //#define int long long using names ......

# 前言 基础数论知识。 original edition 2023.3.29。 upd 2023.6.19：为明天听 zyw 大佬讲课复习，并优化 Latex。 upd 2023.6.20：新增扩展欧几里得，同余最短路，逆元，中国剩余定理。 # 知识点 ## 线性筛 1. 原理：让每个数被它最小质 ......

### 类欧几里德 $\text{令}\space f(a,b,c,n)=\sum_{i=1}^n\lfloor\frac{ai+b}{c}\rfloor$ $f(a,b,c,n)=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac ......

思路：找规律 情况一：尾数为$5$或$0$ 为$5$时进行一次操作变成$0$的情况。 而尾数是 0 时操作无意义，所有数必须相等。 情况二：尾数为 1,3,7,9 可进行一次操作变成情况三。 情况三：尾数为 2,4,6,8 我们通过找规律发现： 2⇒4⇒8⇒16⇒224⇒8⇒16⇒22⇒246⇒12 ......

# 前置知识 ## 积性函数 满足 $f(1)=1$，并且当 $\gcd(a,b)=1$ 时，有 $f(ab) = f(a)f(b)$，则称 $f(n)$ 为积性函数。 如果对于全部的 $a,b$，都有 $f(ab)=f(a)f(b)$，则称 $f(n)$ 是完全积性函数。 ### 常见积性函数 1 ......

# 【题解】[ABC306G] Return to 1 ## 题目链接 [ABC306G - Return to 1](https://atcoder.jp/contests/abc306/tasks/abc306_g) ## 题意概述 本题多测，$T$ 组数据。 对于每组数据，给定一个 $n$ 个 ......

# Mod ## 一、long long 乘法取模 #### 核心思想 用long double 估计商的取值，然后任它溢出,它的真实答案和它%$2^{64}$次方答案是一样的 $x*y$%$m = x*y-\dfrac{x*y}{m}*m$ #### 代码 ```c++ ll mul(ll x,l ......

# Combinatorial Number ## 一、[组合数取模1：](http://oj.daimayuan.top/course/12/problem/524) #### 例题：回答T组询问，输出$C_{n}^{m} \bmod 10^9+7$的值。 $C_{n}^{m} = \dfrac{ ......

# Chinese Remainder Theorem $x≡ai(mod mi)$ **中国剩余定理CRT** ## 1.定义 **Th.** 给出一元线性同余线性方程组 $x ≡ a1 \bmod m1$ $x ≡ a2 \bmod m2$ ... $x ≡ an \bmod mn$ 定理指出假 ......

# Prime sieving and Integer blocking ## 一、Prime number sieve method ### 1.埃氏筛O(nloglogn) 从 2 开始，2是质数，那么2的倍数：4、6、8、10、12、14、16... 肯定不是质数 3是质数，那么3的倍数：6、 ......

## Divisor and Gcd ### 1、算术基本定理：n的质因数分解唯一 一些常见结论： 1.素数无限 2.$\lim_{n\rightarrow+\infty}n\prod\dfrac{n}{\frac{n}{\ln{n}}}$(Π(n)表示 ab|c$ 3.$a|bc,(a,b) = ......

## 数论 ### 小知识复习 整除、质数、线性筛、 $gcd$ 、 $exgcd$ 、逆元、快速幂、费马小定理、（扩展）欧拉定理、卢卡斯定理、中国剩余定理、原根、常见数论函数…… 给一张比较有用的表： ![image](https://img2023.cnblogs.com/blog/304896 ......

比较难,没怎么看懂 //约数: //如果一个数d是n的一个约数,即d能整除n,那么n/d也能整除n: //求所有约数(除法求约数,o(sqrt(n))) #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,x; ......

# 前置知识 ## 积性函数 满足 $f(1)=1$，并且当 $\gcd(a,b)=1$ 时，有 $f(ab) = f(a)f(b)$，则称 $f(n)$ 为积性函数。 如果对于全部的 $a,b$，都有 $f(ab)=f(a)f(b)$，则称 $f(n)$ 是完全积性函数。 ### 常见积性函数 1 ......

// 最基本求一个素数(on),(osqrt(n)) #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; for(int i=2;i<n;i++)//o(n) if(n%i==0){ cout<<"no"; ......

# GCD&LCM&欧拉函——推柿子 ## 一、$\sum_{i = 1}^{n}[\gcd(i,n)=d]$ $\sum_{i = 1}^{n}[\gcd(i,n)=d]$ $=\sum_{i = 1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]$ $=\phi(\f ......

### 求和符号的定义 为了简化形如 $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 ......

## 裴蜀定理 对于任意的整数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 ......