数论ntt

## 欧拉函数 ### 定义与性质 一个数的欧拉函数被定义为**小于等于**$^{①}$该数的与该数互质的数的个数，记作 $\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. 快速的 ......

## 算法 ### 记号 $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^ ......

# 任意模数多项式乘法 > 前言：\ > 在教练讲的时候脑子并不清醒，所以没听懂。后来自己看博客学会了，但目前只学了一种方法：可拆系数FFT。为了方便日后复习，决定先写下这个的笔记，关于三模数NTT下次再补。 > > 建议：准备好演算纸和笔，本篇含有大量推算部分。 > > 注：本篇文章是本蒟写的，d ......

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