博客主页：誓则盟约系列专栏：IT竞赛专栏关注博主，后期持续更新系列文章如果有错误感谢请大家批评指出，及时修改感谢大家点赞

写在前面...通过写数论的md笔记，新知识不确定有没有学懂，但是我的md数学公式方法得到了极大的提升orz质数的定义：针对从2开始的整数定义，如果只包含1和本身这两个因数，则称该数为质数（素数）（1）质数的判定：试除法枚举因数的时候，只枚举到因数比较小的那个范围（根号n）（2）分解质因数：试除法从

素数素数和合数定义若\(p\in\Zeta\)，且\(p\not=0,\pm1\)，其约数集合中的元素只有\(1\)和\(p\)本身，那么称\(p\)为素数。若\(a\in\Zeta\)，且\(a\not=0,\pm1\)，\(a\)不为素数，则为合数。素数一般指正的素数。素数计数\(\pi(x)\)表示小于或等于\(x\)的素

第一章整除1.1基本性质1.1.1同余与整除定义1.1.:设\(a,b\)为整数，若存在一整数\(c\)，使得\(b=ac\)，那么我们说\(a\)整除\(b\)并记作\(a|b\)整除的性质1.2.：1）（反射性）对于所有整数\(a\)，有\(a|a\).2）（传递性）若有\(a|b\)，并且\(b|c\)，那么\(a|c\).3）

萌萌的好数链接：https://ac.nowcoder.com/acm/contest/84851/D来源：牛客网时间限制：C/C++1秒，其他语言2秒空间限制：C/C++262144K，其他语言524288K64bitIOFormat:%lld题目描述萌萌喜欢“好数”，这种“好数“需要满足以下两个条件：1.该数对3取模不为02.该数的最后一位数字

注:\(\logx=\lnx\)组合基础加法原理、乘法原理排列数\(A^m_n=\frac{n!}{(n-m)!}\):从\(1\simn\)选\(m\)个数排成一列的方案数组合数\(C^m_n=\binom{n}{m}=\frac{n!}{(n-m)!m!}\):从\(1\simn\)选\(m\)个数的方案数。(相对于排列数不考虑顺序)

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\)，

数论扩展欧几里得(\(exgcd\))用于求解不定方程\(ax+by=k\)且\(gcd(a,b)|k\)的解。令\(ax+by=gcd(a,b)\)。求\(k\)的话只需要将\(x,y\)乘上\(\dfrac{k}{gcd(a,b)}\)。\[gcd(a,b)=gcd(b,a\%b)\]\[ax_1+by_1=bx_2+(a-\lfloor\dfrac{a}{b}\rfloor\timesb)y_2\]\[ax_1+by

数论分块大部分内容来源于OI-WIKI引理1：\(\\foralla,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\)引理2：\(\lfloor\frac{n}{i}\rfloor\)的取值有\(O(\sqrtn)\

数论分块若可以\(O(1)\)计算\(f(r)-f(l)\)，那么就可以\(O(\sqrtn)\)计算\(\sum^n_{i=1}f(i)(g\lfloor\frac{n}{i}\rfloor)\)。关于\(l,r\)的含义与计算：含义：\(\forallx\in[l,r],\lfloor\frac{n}{x}\rfloor\)相等计算：刚开始\(l\)肯定为\(1\)，如何理解\(r=

乘法逆元若\(a\timesb\equiv1(\bmod\c)\)，且\(\gcd(a,b)=1\)，那么我们定义\(a\)为\(b\)的逆元，也可以称\(a\)是\(b\)在\(\bmod\c\)意义下的倒数。费马小定理对于质数\(p\)和任意整数\(a\)，有\(a^p\equiva(\bmod\p)\)。反之，若\(a^p\equiv

欧几里得定理：gcd(a,b)=

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

有点菜，现在才会。之前好多篇都烂尾了，这篇不能了。数论分块往往适合于带有向下取整的题目，即求\(\sumf(i)g(\lfloor\frac{n}{i}\rfloor)\)的值。当经过某些处理后可以\(O(1)\)求出\(f(r)-f(l)\)的值时，数论分块可以\(O(\sqrt{n})\)求出上述式子的值。向下取整\(\lfloor

同步发表前言因为\(2025\)届暑假的时候tad疯狂的在讲课，而且用了很多高端的东西和证明导致我在暑假的时候数论板块几乎没有听懂，所以我决定写下这篇文章不让当时的悲剧重演。本篇文章都只讲结论，因为证明分复杂而且没有什么用，在暑假记住结论就好了，至于证明的坑后面会填。欧拉

题目大意：\(f(x)=\begin{cases}x,1\lex\le9\\f(x的各数位之和),x>9\\\end{cases}\)求\(\sum_{i=1}^{n}f(i)\)。根据打表找规律，我们会发现\(f(x)=(x-1)\bmod9+1\)。所以\(\sum_{i=1}^{n}f(i)\)\(=\sum_{i=1}^{\lfloor\frac{n}{9}\rfloor\cdot9}f(x)+\sum_{i=\l

菜就多练，输不起就别玩，不会就是不会。二项式推论\(1.\)\(\tbinom{n}{m}=\tbinom{n}{n-m}\)\(2.\)\(\tbinom{n}{m}=\frac{n}{m}\tbinom{n-1}{m-1}\)\(3.\)\(\sum\limits_{i=0}^nC_n^i=2^n\)证明：拆\((1+1)^n\)\(4.\)\(\sum\limits_{i=0}^n(-1)^iC_n^i=0\)特殊的，

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

[SDOI2012]Longge的问题我们要求\(\sum\limits_{i=1}^n\gcd(i,n)\)，但\(gcd\)没啥卵用，所以尝试给这n个正整数分组。对于\(gcd(i,n)=1\)的数给他们归到\(G(1)\)这个集合里去，当然，这个集合元素的数量为\(\phi(n)\)。对于\(gcd(i,n)=2\)的数归到\(G(2)\)这个集合里去

从小学我们就知道\(i=\sqrt{-1}\)。复数一般写作\(a+bi\)复数四则运算加法：\((a+bi)+(c+di)=(a+c)+(b+d)i\)减法就是取个相反数。乘法：\((a+bi)\times(c+di)\)\(=ac+(ad+bc)i+bd\timesi^2\)\(=(ac-bd)+(ad+bc)i\)共轨复数\(a+bi\)的共轨复数是\(a-bi\)，它们相

数论进阶原根与阶阶若\(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\)。计算

素性测试素性测试就是判断某个数是否为质数。费马小定理内容：若\(p\)为质数，\(a\)为任意整数，有\(a^{p-1}\equiv1(mod\p)\)那么可以多次随机取一个基数\(a\in(1,p)\)若\(p\)满足上式，那么它为质数的可能性就越大。MillarRabin素性测试inlinellqpow(lla,lln,ll

数论常见筛法对于任意正整数\(A\)，存在唯一集合{\((p_1,q_1),(p_2,q_2),\dots,(p_n,q_n)\)}满足\(A=\prod^n_{i=1}{p_i}^{q_i}\)\(\min(a,b)+\max(a,b)=a+b\)\(\gcd(a,b)\times\operatorname{lcm}(a,b)=ab\)埃氏筛在\(O(n\log\logn)\)时间内预处理出\([1,n]\)内所

埃氏筛P7960[NOIP2021]报数P1835素数密度：区间筛。预处理\(\sqrt{R}\)内的质数，然后用埃氏筛筛[L,R]的质数。线性筛-EOF-欧拉函数P10031「CfzRound3」XorwithGcd光速乘用于解决$$llTimes(lla,llb,llc){ ullt=(longdouble)a*b/c+0.5; llans=(u

概述扩展欧几里得算法(\(exgcd\))可以用来求形如\(ax+by=c\)的不定方程的通解。铺垫-\(\small\texttt{ax+by=gcd(a,b)}\)的解\(exgcd\)的思想是在用辗转相除法递归\(gcd(a,b)\)的回溯时求出对应方程\(ax+by=gcd(a,b)\)的解。考虑方程\(ax+by=gcd(a,b)\)。看回辗