今天才知道这几个定理，网上没搜到证明方式，别人不会证那我就证明一下。定理1：\[\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\]证明：根据\(\gcd\)具有\(\gcd(a,b)=\gcd(a-b,b)\)的性质，不妨设\(m\gen\)，作差有：\[\begin{aligned}\gcd(a^m-1,a^n-1)&=\gcd(a

乘法逆元给定\(n\)个正整数\(a_i\)，求它们在模\(p\)意义下的乘法逆元。逆元是模意义下的倒数，能够将模意义下无法直接计算的除法转化为乘法。先来总结一下常用的求单个逆元的方法：扩展欧几里得\(O(\logn)\)地求一个数的逆元，要求\(a,p\)互质即可（\(p\)为模数），原理为解线性

2、约数一个数能够整除另一数，这个数就是另一数的约数。如2，3，4，6都能整除12，因此2，3，4，6都是12的约数。也叫因数。1、求一个数的所有约数——试除法例题：给定n个正整数ai，对于每个整数ai，请你按照从小到大的顺序输出它的所有约数。输入格式第一行包含整数n。接下来n行，

一、定义   环R中的理想P如果满足以下条件就称作素理想：P是R的真理想（即P≠R），且对任何a,b∈R，如果乘积ab∈P，那么a或b中至少有一个属于P。二、性质基本性质：若P为素理想，则对R中任意两个元a与b，若ab∈P，有a∈P或b∈P。P是R的素理想当且仅当商环R/P是整环。P是R的极大理想当

大家好我是#Y清墨，今天讲的是质数判断和打表。一.质数的相关概念质数的定义除了1和自身，找不到其它因数的数。例如7和13都是质数。最小的质数是2。合数除了1和自身，能找到其它因数的数。例如10,16均是合数。最小和合数是4。特殊情况数字1既不是质数，也不

基础数论Update:2024/11/02。素数素数和合数定义若\(p\in\Zeta\)，且\(p\not=0,\pm1\)，其约数集合中的元素只有\(1\)和\(p\)本身，那么称\(p\)为素数。若\(a\in\Zeta\)，且\(a\not=0,\pm1\)，\(a\)不为素数，则为合数。素数一般指正的素数。素数计数\(\pi(x)

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

linkA显然只需要考虑质因子。首先\(k\)只有一个质因子可以特判，有两个可以exgcd有三个及其以上那么最小的一个\(\le10^5\)，同余最短路即可。B考虑一个序列$\lbracex|x=a_ib_i^t,t\in\mathbb{N}\rbrace$，对于一个质因子提出了怎样的限制？设\(a_i,b_i\)在质因数\(p\)

[复习]数论基础模运算\[(a\pmb)\bmodp=((a\bmodp)\pm(b\bmodp))\bmodp\]\[(a\timesb)\bmodp=((a\bmodp)\times(b\bmodp))\bmodp\]积性函数\[\forall\gcd(x,y)=1,f(xy)=f(x)\timesf(y)\]完全积性函数\[\forallx,y\inN^+,f(xy)=f(x)\timesf(y)\]g

数论分块讲解先咕咕，做杜教筛做错题了做了个数论分块，下次再讲。题目示例P3327[SDOI2015]约数个数和设\(d(x)\)为\(x\)的约数个数，给定\(n,m\)，求\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]对于\(100\%\)的数据，\(1\leT,n,m\le50000\)。\[\sum_{i=1}^n\sum_{j=1}^md(ij)=

蓝月の笔记——数论篇Part0约定令\(\mathcal{P}\)为质数的集合所有时间复杂度均指上界Part1质数，\(\gcd\)质数就是只有\(1\)和本身两个因数的数，公因数就是同时使多个数的因数的数，\(\gcd\)就是最大的公因数质数求法：欧拉筛在埃氏筛的基础上优化，让每个合数都只被一个

引言        在前面的课程中，我们已经学习了Python的基本输入输出、数据类型及其转换、顺序结构、分支结构、循环结构、循环控制语句、字符串类型、列表类型、元组类型、字典类型、集合类型、函数的定义与使用、函数调用与作用域、函数的高级应用、质数、倍数与余数

一、最大公约数定义不全为\(0\)的整数\(a,b\)的最大公约数是指能够同时整除\(a\)和\(b\)的最大整数。欧几里得算法(gcd)gcd是用来求解两个整数的最大公约数定理1.2.1对于整数\(a,b,m,n\)，若\(c\mida，c\midb\)，则\(c\mid(ma+nb)\)证：\(\becausec\mida

同余定理同余性质同余性质是指在任意情况下，都有：$n\timesm\bmodp$=$(n\bmodp)\times(m\bmodp)\bmodp$$n+m\bmodp$=$(n\bmodp)+(m\bmodp)\bmodp$$n-m\bmodp$=$(n\bmodp)-(m\bmodp)\bmodp$除法不满足同余性质。欧拉定理欧拉函数：$\varphi(n)$表示在$1$和$n

由于做莫反题需要大量的基础函数知识，于是有了这篇文章将我做到的函数都记录下来。持续施工中。约数和函数\(\sigma\)定义：\(\sigma(x)=\sum_{d|x}d\)。证其为积性函数：设\(x=\prodp_i^{a_i}\)，设\(d\)为\(x\)的质因数个数，那么发现：\[\begin{aligned}\sigma(x)&=\sum_{i

前置需求数论分块概念对于一个形如\(\sum_{x=1}^n\lfloor{\frac{n}{x}}\rfloor\)的式子，我们发现对于一部分的\(x\)，它们的\(\lfloor{\frac{n}{x}}\rfloor\)值相同，因此我们没必要\(\mathcal{O(n)}\)计算，可以采用数论分块的办法将这一步的复杂度降低至\(\mathcal{O(\sqrt

1.欧拉函数我们定义\(\varphi(n)=\sum^n_{i=1}[\gcd(i,n)==1]\)。特殊的当\(n\)为质数的时候，\(\varphi(n)=n-1\)。假如我们定义\(n=p_1^{a_1}\timesp_2^{a_2}\times\cdots\cdots\timesp_k^{a_k}\)，那么\(\varphi(n)=n\times\dfrac{p_1-1}{p_1}\t

数论分块1.0可以快速计算一些含有除法向下取整的和式（形如$\sum_{i=1}^ng(i)\left\lfloor\frac{n}{i}\right\rfloor$）。2.0引理1：\(\left\lfloor\frac{n}{i}\right\rfloor\)的取值最多只有\(2\times\sqrtn\)种。证明：对于\(i\le\left\lfloor\sqrtn\rig

好久不见，开学和假期天天搞csp实在没时间搞CSDN,终于抽出一点时间来写会文章了。我们先来看一道NOIP提高组的题目题目描述小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在

【OI-wiki#5805】feat(math/number-theory/sqrt-decomposition.md):增加数论分块的拓展&改动部分格式以计算含有\(\left\lfloor\sqrt{\frac{n}{d}}\right\rfloor\)的和式为例。考虑对于一个正整数\(n\)，如何求出集合\[S=\left\{\left\lfloor\sqrt{\frac{n}{d}}\right\rf

数论基础数论函数数论函数是指这样一类函数：其定义域是正整数，值域是一个数集。定义两个数论函数的加法，为逐项相加，即\((f+g)(n)=f(n)+g(n)\)。定义数乘这个数和每一项都相乘，即\((xf)(n)=x\timesf(n)\)。常见数论函数\[1(x)=1\\\epsilon(x)=[x=1]\\id(

从莫比乌斯反演的文章里迁移出来的。部分数论函数结论的证明前面的小节中，我们使用了一些数论函数相关的结论，但并未给出证明。接下来我们来证明它们。欧拉函数证明\[\varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\]由欧拉函数公式，设\(x

6.初等数论6.1初等数论概念若整数\(b\)除以非零整数\(a\)（\(b\)为被除数，\(a\)为除数）的余数为\(0\)，则称\(a\)整除\(b\)或\(b\)能被\(a\)整除。记作\(a\|\b\),\(a\)叫做\(b\)的约数（因数），\(b\)叫做\(a\)的倍数。\(a^b\)(\(b\)位非负整数)表示

积性函数一般我们只需要考虑定义域在\(\mathbb{Z}\)就够了，什么实数，复数都不用管。如果函数\(f(x)\)满足对于任意的\(a,b\)且\(\gcd(a,b)=1\)，都有\(f(ab)=f(a)f(b)\)。欧拉函数\(\varphi(i)\)\(\varphi(n)\)定义为大于等于\(1\)且小于\(n\)且与它互质的数的个数

数学是毒瘤基础数论总结。数论题的代码都是一个个板子拼起来的，本博客只放板子。声明：本博客中出现的所有代码，都视为加入了#defineintlonglong数论题的特点题目大意简洁易懂。但有的题还是会古舟一堆码量小，全是板子极其难想，需要手推公式longlong是标配筛