阶先看看啥是阶.由欧拉定理可知,对于\(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=

[AGC066A]AdjacentDifference考虑我们生成的矩阵中的数都是\(d\)的倍数我们显然只需要保证\(a'_{i,j}=xd\)中的\(x\)互不相同即可我们钦定根据\(i+j\)的奇偶性来设置\(x\)为\(0\)或\(1\)，\(a_{i,j}\equivxd\pmod{2d}\)我们尝试只对\(x=0\)时分析它此时的代

1同余1.若\(a\equivb\pmodm\)，当且仅当\(m\mid(a-b)\)2.同加性：若\(a\equivb\pmodm\)，则\(a+c\equivb+c\pmodm\)3.同乘性：若\(a\equivb\pmodm\)，则\(a*c\equivb*c\pmodm\) 若\(a\equivb\pmodm,c\equivd\pmodm\)，

数学是科学的女皇，数论是数学的女皇。——高斯\[\Huge{\Large{}}\mathcal{Q\!\!\!X}\]\(\text{Gcd}\&\text{Lcm}\)最大公因数和最小公倍数，基本上都是一些杂题。这里有一个性质：\[\text{lcm}(a,b)=\frac{ab}{\gcd{(a,b)}}\]这个东西是可以证明的。设有可重集合\(A,B\)

ABC207EModi显然有\(n^3\)的dp。设\(f_{i,j}\)表示前\(i\)个数里划分\(j\)段（\(i\)为第\(j\)段结尾）的方案数，\(s_i=\sum_{i=1}^ia_i\)，则有：\[f_{i,1}=1,f_{i,j}=\sum_{k=1}^{i-1}[s_i-s_k\equiv0\pmodj]f_{k,j-1}\]考虑进一步优化。我们发现上式可以化为：\[f_{

阶与原根阶若正整数\(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\)

2024.4.29【锦水汤汤，与君长诀！】Monday三月二十一数论专题同余oi.wiki!除法定理对于任何整数a,和正整数m，存在唯一整数q，r，使得满足\(0\ler<m,a=qm+r\)其中$$q=\lfloor\frac{a}{m}\rfloor$$为商，\(r=a\mod\m\)为余数余数将amodm记作余数同余如果\(a\mo

题意：解方程\[a^x\equivx\pmodm\]数据范围：\(a<m\le10^9\)Solution首先\(a^x\equiva^{x\bmod\varphi(m)+\varphi(m)}\pmodm\)我们设\(\text{solve}(\&x,y,m)\)表示解决\[a^{x\bmod\varphi(m)+y}\equivx\pmodm\]原题即\(\text{solve}(\&x,

【多项式求逆】【整式取模】定义单项式取模。\[C\cdotx^k\bmodx^n=\begin{cases}0&k\gen\\C\cdotx^k&k<n\end{cases}\]定义多项式取模为它的每一项取模相加。可以看出，模\(x^n\)相当于保留\(0\simn-1\)次项。【问题描述】一般形式：已知多项式\(A(x),C(x)\)，求\(B(x

很容易想到，\(n\)个8可以转换为\((10^{n+1}-1)/9*8\)容易你个集贸啊，xzz推10分钟我推了一个上午顺便膜拜xzz然后就是推式子了。。。(悲\[(10^{n+1}-1)/9*8\equiv0\pmodh\\=>{10^{n+1}*8-8\above1pt9}\equiv0\pmodh\\=>10^{n+1}*8-8\equiv0\pmod{9h}\\=>10^{n+1}*8\e

多项式求逆考虑倍增。若已经求出\(A\timesB'\equiv1\pmod{x^n}\)，我们希望求出\(B\)使得\(A\timesB\equiv1\pmod{x^{2n}}\)。有：\[B-B'\equiv0\pmod{x^n}\]\[(B-B')^2\equiv0\pmod{x^{2n}}\]\[B^2-2BB'+B'^2\

求逆元费马小定理扩展欧几里得线性求逆元中国剩余定理形如\[x\equiva_1\pmod{n_1}\]\[x\equiva_2\pmod{n_2}\]\[x\equiva_3\pmod{n_3}\]\[x\equiva_4\pmod{n_4}\]OI-WIKI点击查看代码LLCRT(intk,LLa[],LLr[]){LLn=1,ans=0;

上午就磨着rec，直到在实验室搬完砖后与rec成功结合为recain，被进行了一场启发式教学题目p=8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229q=1264067497399

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

1.同余1.1同乘性\({\displaystylea\equivb{\pmod{m}}}\)\({\displaystylec\equivd{\pmod{m}}}\)则\({\displaystylea*c\equivb*d{\pmod{m}}}\)证明\({a=k_1m+x}\);\({b=k_2m+x}\)\({c=k_3m+y}\);\({d=k_4m+y}\)\({a*c=k

快速幂$$\5*e\equiv1\pmod7\e=5^{7-1-1}快速幂\a\equiva^{p}\pmod{p},assert\p\is\prime费马小定理\a*a^{p-2}\equiv1\pmod{p}$$dp泄露$$已知e,dp,c,n\ed\equiv1\pmod{phi}\dp=d\mod{p-1}\ed-1=k_1(q-1)(p-1)\d=k_

倒叙总结。link[tag:构造，数论]正着做很困难，正难则反，现在考虑一个数\(a_x\)能否作为结尾，显然要满足\(F(x)=lcm\{a_i|i\neqx\}\)的\(F(x)\)不是\(a_x\)的倍数。在考虑不断取到最后一个数的过程中，\(F(x)\)显然不会上升，可以使用任意顺序的意思。现在还有一个问题，\(F(

昨天放假回去得知我对象给我买了一个重云的吧唧，真的好可爱啊

SatLGR-176（Div.2）A.区间和问题，一眼盯真：前缀和。B.bfs，顺便记一下转移方向。C.最小化最大值，二分答案，用点DS实时维护逆序对即可，笔者用了线段树。D.区间DP，预处理一下\(a_i^{a_j}\)的值，然后记\(f_{l,r,0/1}\)表示到达了\([l,r]\)区间，并且最后一步是取了头部/尾部到达该

传送门显然每一只龙对应了唯一的一把剑。用multiset可以求出每一把剑。于是题目就变成了：\[\begin{cases}b_1x\equiva_1\pmod{m_1}\\b_2x\equiva_2\pmod{m_2}\\\dots\\b_nx\equiva_n\pmod{m_n}\end{cases}\]如果\(b_i=1\)，直接EXCRT即可。现在\(b_i>1\)，还是以EXCRT

授课老师：ybx、chh。授课时间：2024/3/8。授课内容纲要：勒让德符号及其性质（欧拉准则，高斯引理，二次互反律）。勒让德符号概括好像在OI和MO当中都挺有用的。勒让德符号的定义假设\(p\)为奇质数，\(a\inU_p\)（\(U_p=\{1,2,\dots,p-1\}\)），则：\[\left(\dfracap\right)=\begin{cases}

嗯，这就是小学难度，起码我学这些东西的时候我是个小学生线性求逆元这个玩意要分两块讲，\(p\)是模数。线性求\(1\simN\)的逆元对于一个\(i\)：\[\text{设}a=\lfloor\frac{p}{i}\rfloor,\b=p\bmodi,\]\[ai+b\equiv0\pmodp,\]\[\frac{i}{b}+\frac{1}{a}

普通的CRT只能处理模数两两互质的情况，而EXCRT可以求得任意情况下同余方程组的通解。思想：把两个同余方程合并成一个，直到剩下一个。考虑两个同余方程\(x\equivp_1\pmod{m_1},x\equivp_2\pmod{m_2}\)。则\(x=p_1+m_1A=p_2+m_2B\)。移项得\(m_1A-m_2B=p_2-p_1\)。这是

P3306Solutionlink\(x_{i+1}\equiva\timesx_i+b\pmodp\)\(x_{i+1}\equiva(ax_{i-1}+b)+b\pmodp\)\(x_{i+1}\equiva(a(ax_{i-2}+b)+b)+b\pmodp\)\(...\)\(\displaystylex_{i+1}\equiva^ix_1+b\sum\limits_{j=0}^{i-1}a^j\pmodp\)即