质数唯一分解定理任意一个正整数都可以唯一地表示成若干个素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。埃氏筛要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。时间复杂度\(O(nlogn)\)a[1]=1;

一、定义    设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。其中，φ(m)表示m的欧拉函数，即小于或等于m的正整数中与m互质的数的数量。二、性质生成性：若g是模m的一个原根，则g可以生成模m的所有可逆元。也就是说，对于任意与m互质的整数a，都可以找到正整

别样的\(\text{NOI}\)模拟赛。\(A\)十几分钟能写完的随机化都放过去了，\(B\)题面的代码\(CE\)了，\(C\)边分治的思路仅闪过一瞬就忘了。A.离散猜数你说得对，但是若答案正确，且你的代码使用的询问次数为\(x\)，std使用的询问次数为\(y\)，计算\(c=\dfrac{x}{y}\)。若\(c\l

这篇博客只是听绿用来整理思路的胡言乱语，包含大量主观臆断，很多观点其实十分浅显甚至错误，各位大佬就当看个乐子即可，欢迎狠狠拷打听绿写这篇博客其实挺痛苦，终稿也是删删减减后有一定把握的内容(也不能总误导人不是），很多联系听绿并没有想清楚，希望在日后学习思考中能够对这些知识能够

前言椭圆曲线配对，是各种加密构造方法(包括确定性阀值签名、zk-SNARKs以及相似的零知识证明)的关键元素之一。椭圆曲线配对(也叫“双线性映射”)有了30年的应用历史，然而最近这些年才把它应用在密码学领域。配对带来了一种“加密乘法”的形式，这很大的拓展了椭圆曲线协议的应

1.复数1.1复数的引入和定义1.1.1略谈数集扩充略了很多字。在数学在现实应用领域的发展过程中，我们常需要解类似的方程：\(x^2+a=0\)，然而这在实数集下无解。1.1.2虚数单位于的引入与复数的定义于是虚数单位"i"被引入，并且有\(i^2=-1\)。让复数表示为实数与虚数的

定义阶：对于\(a\perpm\)，定义阶\(\delta_m(a)\)表示最小的\(i\)满足\(a^i\equiv1\pmodm\)。原根：对于\(a\perpm\)，\(a\)是\(n\)的原根当且仅当\(\delta_m(a)=\varphi(m)\)。性质：\(a,a^2,a^3,...,a^{\delta_m(a)}\)互不相同。\(a^i\equiv1\pmod

卡特兰序列\(C_{k}(m,n)\)表示在网格中从\((0,0)\)走到\((m,n)\)时均不经过\(y=x+k\)的斜线即每时每刻满足\(y<x+k\)画图可得\(C_{k}(m,n)=\binom{n+m}{m}-\binom{n+m}{m+k}\)用法：任意前缀和不小于\(-x\)使用\(C_x\)（左括号是\(+1\))反射容斥学

较为冷门(?)的数论知识，但在解决一些特殊问题上有着重要的作用。整数的阶根据欧拉定理有正整数\(n\)和一个与\(n\)互素的整数\(a\)，那么有$a^{\phi(n)}\equiv1\pmod{n}$。因此至少存在一个整数满足这个方程。并且由良序原理可得一定存在一个最小正整数满足这个方程。、

离散对数离散对数的定义方式和对数类似.取有原根的正整数模数\(m\),设其一个原根为\(g\).对满足\((a,m)=1\)的整数\(a\)，我们知道必存在唯一的整数\(0\leqk<\varphi(m)\)使得\(g^k\equiva\pmodm\).我们称这个\(k\)为以\(g\)为底,模\(m\)的离散对数,记作\(k

阶先看看啥是阶.由欧拉定理可知,对于\(a\in\mathbf{Z},m\in\mathbf{N}^*\),若\((a,m)=1\),则\(a^{\varphi(m)}\equiv1\pmodm\).因此满足同余式\(a^n\equiv1\pmodm\)的最小正整数\(n\)存在,这个\(n\)称作\(a\)模\(m\)的阶,记作\(\delta_m(a)\)或\(\opera

原根学习笔记原根这是一个又臭又长的内容。拉格朗日定理：设\(p\)为素数，对于模\(p\)意义下的整系数多项式\[f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\nmida_n)\]的同余方程\(f(x)\equiv0\pmodp\)在模\(p\)意义下至多有\(n\)个不同解。证明：使用归纳法，对于\(n=

\(\text{FFT}\)学习笔记多项式确定一个多项式，往往只需要知道每一次项前的系数是多少即可。众所周知，一个朴素的多项式往往可以被写成\[f(x)=\sum_{n\ge0}a_nx^n\]的形式，在这种形式下的两个多项式\(f,g\)的乘积\(h\)往往可以按照\[h(x)=(f*g)(x)=\sum_{n\ge0}(\sum_{i=0

12奇妙筛法已开工。12.1杜教筛12.2Min-25筛Min_25筛可以在\(\mathcalO\left(\frac{n^{\frac34}}{\logn}\right)\)的时间复杂度内解决一类积性函数前缀和问题。说形象点就是\(1s\)能跑\(10^{10}\)，相当优秀。要求：\(f(p)\)是关于\(p\)的低阶多项式，

阶与原根阶若正整数\(m,\a\)，满足\((a,m)=1\)，则使\(a^n\equiv1\pmodm\)的最小正整数\(n\)称为\(a\)模\(m\)的阶，记作\(\delta_m(a)\)。\(\delta_7(1)=1,\\delta_7(2)=3,\\delta_7(3)=6\)。原根若\(\delta_m(a)=\varphi(m)\)，则称\(a\)

书接上回...我们知道，我们在使用FFT时，靠的是单位根\(\omega\)。数学家证明这是复数域中唯一符合条件的数。可是它的浮点误差和带来的巨大运算时间使我们有点不能接受。于是，我们想想能不能找个替代品替代掉\(\omega\)。于是，原根就出现了！原根的引入阶对于一个数\(x\)，在

阶对于\(\gcd(a,p)=1\)，最小的\(t\)使得\(a^t\equiv1(\bmodp)\)称为\(a\)的阶。写作\(\operatorname{ord}_p(a)\)。若\(a^k\equiv1(\bmodp)\)，当且仅当\(\operatorname{ord}_p(a)|k\)。求阶的复杂度是\(O(\sqrt{n})\)。给定\(\gcd(a,p)=\gcd(b,p)=1\)，问是否存在

数论进阶原根与阶阶若\(a,p\)互质，定义\(a\)在模\(p\)意义下的阶为最小的正整数\(t\)满足\(a^t\modp=1\)。\(a\)在模\(p\)意义下的阶记作\(ord_p(a)\)，\(a^{ord_p(a)}\modp=1\)。对于整数\(k\)，\(a^k\equiv1(\modp)\)当且仅当\(ord_p(a)|k\)。计算

前言我曾今写过一篇标题一模一样的文章，但是那篇都是在抄书，写的太烂了。在此重构。模意义是什么？即小学学过的"余数"：\(13\)除以\(5\)商\(2\)余\(3\)。那么\(13\bmod5=3\)（\(\bmod\)读作模）。如果有两个数\(a,b\)除以一个数\(p\)的余数一样，则我们称\(a,b\)关于

原根&离散对数阶设\(m>1\)\(\gcd(a,m)=1\)，使\(a^r\equiv1(mod\m)\)的最小\(r\)是\(a\)对\(m\)的阶，记作\(\delta_m(a)\)定理一：设\(m>1\)，且\(gcd(a,m)=1\)，\(a^n\equiv1(mod\m)\)，则\(\delta_m(a)|n\)定理一推论：\(\delta_m(a)|\phi(m

NTT好吧，本质上就是FFT，把单位根换成了原根（不是很理解但是就是记住就行）优点能取模，FFT的复数你给我来取个模没有精度差，FFT浮点数的精度怎么也会出一点问题由于均为整数操作（虽然取模多），NTT常数小，通常比一大堆浮点运算的FFT要快缺点多项式的系数都必须是整数模数有限制，NTT题的模

目录原根阶阶的定义与基本性质原根原根的定义与基本性质原根判定性定理原根存在性定理原根的求法枚举法（最小原根）枚举法（所有原根）指标指标的定义与基本性质指标的求法BSGS算法扩展BSGS算法原根阶阶的定义与基本性质定义设\(a\in\Z,m\in\N^*\)且\(\gcd(a,m)=1\)，那么

快速数论变换|NTT初学前置FFT原根阶：称满足同余方程\(a^x\equiv1\modm\)的最小正整数解\(x\)为\(a\)的模\(m\)的阶，记为\(Ord_ma\)。观察到本质就是最短循环节，同时该同余方程类似于欧拉定理：\[a^{\varphi(m)}\equiv1\modm，a\botm\]那么显然两者的关系是

1.整除、欧几里得除法的的定义好像别的没啥好说的，就挑点自己记不太清的写上来.1.1Eratosthenes（厄拉托塞斯）筛法该方法用于快速获得小于整数N的素数集合，工作原理如下：对寻找小于整数N的素数，先求\(\sqrt{N}\)（没法取整就写成\(\sqrt{N}<[\sqrt{N}]+1\)的形式）,获取小于\(\sqrt{N}

T1题意：已知\(P=10^{18}+31\)为质数且存在原根\(g=42\)，记\(A_0\)为\(795484359100928850\)，\(A_k=f(A_{k-1})\)，其中\(0<f(x)<P\)且满足\(g^{f(x)}\equivx(modP)\)，可证明这样\(f(x)\)唯一存在，每次查询一点\(f(x)\)的取值，\(1\lex\le10^5\)。事实上，此