组合数学组合数定义式\(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)，表示\(n\)个数中选\(m\)个。下降幂\(n^{\underline{m}}=n(n-1)(n-2)\cdots(n-m+1)\)上升幂\(n^{\overline{m}}=n(n+1)(n+2)\cdots(n+m-1)\)相关结论\(n^{\overline{m}}=(n+m-1)^{\un

P3518[POI2011]SEJ-StrongboxDescription有一个密码箱，\(0\)到\(n-1\)中的某些整数是它的密码。且满足：若\(a\)和\(b\)是它的密码，则\((a+b)\bmodn\)也是它的密码（\(a\)，\(b\)可以相等）。某人试了\(k\)次密码，前\(k-1\)次都失败了，最后一次成功了。问，该密码箱最多有多

CF516EDrazilandHisHappyFriendsDescription有\(n\)个男生\(m\)个女生，编号分别为\(0\simn-1\)和\(0\simm-1\)。有\(B\)个男生和\(G\)个女生是快乐的，其他人是不快乐的。在第\(i\)天，编号为\(i\bmodn\)的男生和编号为\(i\bmodm\)的女生会一起

学原根发现拔山盖世算法忘光了，干脆一块儿写了吧。\(BSGS\)算法\(BSGS\)算法，又名拔山盖世算法、北上广深算法。他解决的问题如下：求解最小的可行的\(k\)，满足\(a^k\equivb(\bmodp)\)，其中保证\(\gcd(a,p)=1\)。容易想到暴力枚举，时间复杂度\(O(p)\)，但是巨劣，考虑优化。

Codeforces题解-[CodeforcesRound867(Div.3)-D.Super-Permutation]题目链接题目描述Apermutationisasequence\(n\)integers,whereeachintegerfrom\(1\)to\(n\)appearsexactlyonce.Forexample,\([1]\),\([3,5,2,1,4]\),\([1,3,2]\)areper

前言在讲中国剩余定理的时候，没有系统性的讲一遍乘法逆元，所以有了这一期专栏。定义如果有一个线性同余方程\(ax\equiv1\pmod{p}\)，则称\(x\)为\(a\equivp\)的乘法逆元。记作\(a^{-1}\)。但是，只有当\(\gcd(a,p)=1\)时，乘法逆元才存在。求乘法逆元费马小定理如果\(\gc

一、欧拉函数1.欧拉函数的意义\(\phi(n)\)表示从\(1\)到\(n\)所有与\(n\)互质的数的数量。表达式为：\(\sum\limits_{i=1}^{n}[\gcd(i,n)=1]\)。2.欧拉函数的通解公式\(\phi(n)=n\prod\limits_{i=1}^{k}(1-\frac{1}{p^i})\)（\(p_i\midn\)，\(p_i\)为素数，\(k\)为小于等于

modularEquation考虑求解多项式同余方程f(x)=0

定理内容对于任意不全为\(0\)的整数\(a,b\)，方程\(ax+by=\gcd(a,b)\)一定有整数解\(x,y\)。证明引理\(1\)对于两个正整数\(a,b\)满足\(a>b\)可以推出\(\gcd(a,b)=\gcd(b,a\bmodb)\)。设\(a=kb+c,d\mid\gcd(a,b)\)，那么一定有\(d\mida,d\midb\)。通过移项可以

大致题意你有一个\(n\)个点的有向完全图。每个点有两个属性\(a_i\)和\(b_i\)。\(u\tov\)的边的权值是\((a_u+b_v)\bmodm\)。给你\(n\),\(m\)和\(\{a_i\}\)以及\(\{b_i\}\),求\(1\)到\(n\)的最短路。$2\\leq\N\\leq\2\\times\10^5$$2\\leq

1.概述   DH（DiffieHellman）密钥交换协议是一种在不安全的通信信道上，通过公开信息安全地交换密钥的方法。它由WhitfieldDiffie和MartinHellman在1976年提出，是密码学领域的一个重要突破，使得在开放网络环境下安全地建立共享密钥成为可能。2.工作原理   基础数学概念

下标默认是在\(\bmod\n\)意义下的。考虑到如果\(a_i>b_i\)那么不可能只操作\(a_{i-1}\)使得\(a_i\)合法，因为这只增不减。于是这说明当\(a_i>b_i\)时一定会操作\(a_i\)使得\(a_i\leb_i\)。但是同时如果\(b_i-a_i\)太大了，\(a_{i-1}\)就不一定能操作

##二次剩余>这东西挺有意思的。###问题>给定$n,p$，求方程$x^2\equivN\bmodp$的解。>>保证$p$是奇素数。####1.判断一个$N$是否是二次剩余(方程解的个数)根据费马小定理，对于任意非$0$整数$x$都有$x^{p-1}\equiv1\bmodp$。则$x^{p-1}\equivx^{2{\fra

省选数学专题开题顺序：\(E\)\(A\)[AGC058D]YetAnotherABCString\(B\)[ABC330G]InversionSquared\(C\)[ABC241Ex]CardDeckScore\(D\)[ABC226H]RandomKthMax\(E\)[AGC016C]+/-Rectangle观察样例容易得到一种构造方式为任意\(h\)行\(w\)列子矩形的权

同余定义若整数\(a,b\)除以正整数\(m\)的余数相等，则称\(a,b\)模\(m\)同余，记为\(a\equivb(\bmodm)\)。同余类和剩余系对于\(\foralla\in[0,m-1]\)，集合\(\{a+km\}(k\in\mathbb{Z})\)的所有数模\(m\)同余，余数都为\(a\)，该集合成为一个模\(m\)

我们知道，扩展欧拉定理的内容如下：\[a^b\equiv\begin{cases}a^b&b<\varphi(m)\\a^{(b\bmod\varphi(m)+\varphi(m))}&b\ge\varphi(m)\end{cases}\pmodm\]但是又有多少人会它的证明呢？也许大佬们一看到就会证了，但是我刚刚才会，不得不说oi-wiki上的证明是真屎。首先第一种情况

题意给定\(n,k,x,y\)和\(2n\)个整数\(x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}\)。找到最小的非负整数\(m\)，使得存在\(2m\)个实数\(x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'\)满足以下条件，或报告不存在这样的\(m\)：\(\sum\limits_{i=0}^{m-1}

更新日志2024/12/08：开工。欧几里得算法用途与原理欧几里得算法，用于求两个数的最大公约数。其核心原理为：\(\gcd(a,b)=\gcd(b,a\bmodb)\)证明首先，我们证明\(\gcd(a,b)=\gcd(b,a\bmodb)\)。为了方便证明，这里我们令\(a>b\)。\[\because\gcd(a,b)\mida\text,\gcd

多项式学习笔记目录多项式学习笔记多项式乘法逆多项式乘法逆给出\(F(x)\)，求\(G(x)\)使得\(F(x)G(x)\equiv1(\bmodx^n)\)。首先\(G_0(x)=\frac{1}{F_0(x)}\)，然后考虑倍增，用\(\bmodx^{\left\lceil\frac{n}{2}\right\rceil}\)的答案推\(\bmodx^n\)的答案：\[

Pohlig-Hellman算法——用中国剩余定理考虑离散对数问题除了作为定理和算法外，建议读者将中国剩余定理看作一种思维方式。如果$m=m_1\cdotm_2\cdot\cdots\cdotm_t$是一组两两互质的整数的乘积，那么中国剩余定理告诉我们，求解关于$m$的方程实际上等价于分别求解关于

喵喵喵~众所周知：$a^b\equiv\begin{cases}a^b&b<\varphi(m)\a^{b\bmod\varphi(m)+\varphi(m)}&b\ge\varphi(m)\end{cases}\pmodm$。同时，当$n>2$时，有$2\mid\varphi(n)$以及$\varphi(2kn)=2\varphi(n)\le\dfrac{\varphi(n)}2(2\nmidn)$。

[杂题]2024.9~2024.11杂题总结题目做多了，不总结，和没做是一样的。ARC061B挺好的一道题。观察到三个不好做，我们想能否搞成一个牌堆去取。发现显然是可以的，我们只需要知道一个确定的取出来牌的编号序列，必然可以确定三者的牌堆分别是什么。所以，问题转换成了：有多少个序列，当\(A\)

复盘T1一眼不会。模拟样例的时候好像得到了一个对于每次询问\(\mathcalO(n)\)做的暴力算法。不太清楚。画了点图。差不多得到一点想法。发现用set维护连通块，总复杂度\(\mathcalO(n\log^2n)\)，1e6肯定过不去。但应该能过80。写写试试。然后写了一坨。实际上这个时候

Description给定一个长度为\(n\)的整数序列\(a_1\sima_n\)，其中的元素两两互不相等。有\(q\)个询问，每个询问给定一个区间\([l,r]\)，你要选择三个下标\(i,j,k\in[l,r]\)满足\(i\neqj,j\neqk,k\neqi\)，最大化\((a_i\bmoda_j)+(a_j\bmoda_k)+(a_k\bmoda_i)\)的值。

9915,9870这是一年前写的：https://www.becoder.com.cn/article/14590。现在我在其基础上，再补充这一年做的一些新题。力推：https://www.cnblogs.com/rainybunny/p/15398779.html。我先逗大家乐一下：Ad-hoc题可能不一定能找出实力最强的选手，但一定能找出最适合做出题人npy的