给定\(a,b,p\)。求最小非负整数\(x\)使得\(a^x\equivb\pmodp\)，或报告无解。保证\((a,p)=1\)。首先根据欧拉定理，\(a^x\equiva^{x\bmod\varphi(p)}\bmodp\)。所以最优的\(x\)一定不大于\(\varphi(p)\)。换一个比较松上限\(p\)。不妨先随便找一个数\(k\)

以下所有分数默认取整。CRT有\(\begin{cases}x\equiva_1\pmod{p_1}\\x\equiva_2\pmod{p_2}\\\cdots\\x\equiva_n\pmod{p_n}\end{cases}\)，且所有\(p\)互质。令\(p'_i=\dfrac{\prodp}{p_i}\)，且\(p'_i\)在\(\bmodp_i\)意义下逆元为\(q_i\)，则

勒让德多项式的正交性对于不同项的勒让德多项式：\[\begin{cases}(1-x^2)P_n''(x)-2xP_n'(x)+n(n+1)P_n(x)\equiv0,\quad(1)\\(1-x^2)P_m''(x)-2xP_m'(x)+m(m+1)P_m(x)\equiv0,\quad(2)\end{cases}\]证明其正交性：\(\int_{-1}^1\{(1)\timesP_

一、数组版本数组版本和poly版本都只涵盖目录中第\(4\sim10\)部分。namespacePoly{intp[maxn],q[maxn],r[maxn],w[maxn];intinum[maxn];intqpow(inta,intk){intres=1;for(;k;a=1ll*a*a%mod,k>>=1)if(k&1)res=1ll*res*a%

EXGCD和EXCRT前言我与这两个算法有很深的渊源。第一次遇到是三年前的五校联考，\(\text{t1}\)需要用到，于是我成了全场唯一一个没切\(\text{t1}\)的。第二次是两年前湖南省集，我依稀记得这是第二场的\(\text{Day1T2}\)，我花了\(\text{2.5h}\)去推\(\text{exCRT}\)的式子

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

多项式的表示系数表示法即\(F(x)=a_0x^0+a_1x^1+...+a_nx^n\)点值表示法一个\(n\)次多项式可以被\(n+1\)个点唯一确定可以用这\(n+1\)个点表示该多项式多项式卷积\[(f*g)(x)=\sum_{i=0}^{n}\sum^n_{j=0}a_ib_{j}x^{i+j}\]说白了就是暴力展开快速傅里叶变换（FFT）单位根对

椭圆曲线离散对数问题（Ellipticcurvediscretelogarithmproblem，ECDLP）对于ECC系统而言，一般会希望\(♯⁡E⁡(F_q)\)尽可能地接近素数。这是因为攻击者面临的ECDLP其（渐进）复杂度取决于\(E⁡(F_q)\)的最大素数子群的大小。即便椭圆曲线上离散对数问题的实现使用产生整个群的基点（ge

卢卡斯定理对于非负整数\(a\)，\(b\)和质数\(p\)，有\[C_{a}^{b}\equivC_{a~mod~p}^{b~mod~p}\cdotC_{\lfloor{a/p}\rfloor}^{\lfloor{b/p}\rfloor}~~\left({mod~p}\right)\]证明引理\[\left({1+x}\right)^{p^{\alpha}}\equiv1+x^{p^{\alpha}}~~\left(

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

多校A层冲刺NOIP2024模拟赛12\(T1\)A.Alice和璀璨花\(65pts/65pts/65pts\)部分分测试点\(1\sim10\)：设\(f_{i,j}\)表示前\(i\)位中生长趋势子序列长度为\(j\)时的末尾最小元素，然后进行暴力转移。测试点\(11\sim13\)：观察到至多选择\(\left\lceil\log_

RSA算法详解及相关数学原理解析前言‍为了记录自己学习密码学的过程，也是为了便于个人应付相关课程的考核，故写此博客。本博客总结了怎么用C++手搓一个RSA算法，以及补补欠缺的一些数学知识和可能欠缺的一些其他算法的实现。参考了其他人的相关博客，用便于我自己理解的话和方式和

BSGS对于高阶同余方程的求解通过题目给出的式子\(x_{2}\equiva*x_{1}\modp\)\(x_{2}+\frac{b}{a}\equiva*x_{1}+\frac{b}{a}\modp\)\(x_{3}=a*x_{2}+b\equiv(a^2)*x_{1}+a*b+b]\modp\)\(对该式子进行继续推导可以得出\)\(x_{i}=a^{i-1}*x1+\sum_{j=0}^{i-2}a^{j}

简要题意给定一个\(n\timesn\)矩阵，矩阵中的每一个元素的计算方式如下：随机从\([0,n-1]\)中选出两个整数（可以重复）\(a,b\)，矩阵的元素为\(a\timesb\bmodn\)求矩阵中元素\(m\)出现次数的期望。\(0\lem<n\le10^{12}\)题解对于矩阵中的任意一个元素是独

原题链接\(首先我们来简单地复习一下中国剩余定理\)\(对于x\equiva_i\modm_i\)\(令M=\prod_{i=1}^{n}m_i（其中m_i代表的是除数，a_i代表的是余数）\)\(M_i=M/m_i\)\(t_i\equiv(M_i)^-1\modm_i（使用扩展欧几里得算出即可exgcd）\)\(因为(t_i*M_i)\equiv1\modm_i并且

A数学题，不会。随便取一数\(v\)，询问得到\(t\equiv\log_gv\pmodp\)。我们希望找到\(x\)使得\(v^x\equivg\pmodp\)，即\(g^{tx}\equivg\pmodp\Leftrightarrowtx\equiv1\pmod{p-1}\)。那么只要\(t\)与\(p-1\)互质即可求得逆元。有原根相关知识可以知

ARC185A-modMGame2简要题意Alice和Bob玩卡牌游戏。每个人都有一副\(N\)张卡牌，分别标上数字\(1\simN\)。现从Alice开始，两人轮流出牌放入牌堆，每人每局恰好出一张牌，出过的牌不能再出；如果在某一时刻，牌堆里所有牌的数字总和是\(M(N<M)\)的倍数，则刚刚出牌的玩家输，

本文于github博客同步更新。A：考虑随便取一个数\(v\)，用一次询问问出\(t=\log_gv\)。我们希望找到一个\(x\)使得\(v^x\equivg\pmodp\)，也即\(g^{tx}\equivg\pmodp\ifftx\equiv1\pmod{p-1}\)。于是，我们希望找到的\(v\)使得\(t\)与\(p-1\)互质即可。由原根的

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

[ARC185A]modMGame2题意Alice和Bob每人手里有\(n\)张牌，牌上有数字\(1,2,\cdots,n\)，从Alice开始轮流出牌，若一个人出牌后场上牌数字的总和能被\(m\)整除，则这个人输掉，若两人的牌都出完后还没有人输，则Alice获胜。给出\(n,m\pod{n<m}\)，问两人都进行最优操作后谁会

每次复习完下一次都会忘，这次下定决心一定要记下来！！！FFT和NTT板子，直接拿过来（包括了其他的定义）：intn,m,rev[maxn];intqpow(intx,intk,intp){ intres=1; while(k){ if(k&1) res=res*x%p; k>>=1,x=x*x%p; } returnres;}voidprepare(

EC(EllipticCurve)椭圆曲线三种椭圆曲线一般资料会以维尔斯特拉斯曲线（WeierstrassCurve）为例介绍椭圆曲线的基本概念和运算原理，这是因为任意椭圆曲线都可以写为维尔斯特拉斯曲线形式。实际上，椭圆曲线还包括多种其他的类型，如蒙哥马利曲线（MontgomeryCurve）、扭曲爱德华曲线（Twiste

离线\(O(1)\)求逆元求出\((\prodx)^{-1}\)即可。线性求逆元先线性求逆元预处理出\(x\leB\)的\(x^{-1}\)，设为\(inv_x\)。对于一个\(x\)，令\(p=qx+r\)。\[0\equiv0\pmodp\to0\equivp\equivqx+r\tox^{-1}\equiv-q\cdotr^{-1}\]在线\(O(1)\)求逆元

炼石计划9月10日NOIP模拟赛#2【补题】-比赛-梦熊联盟(mna.wang)模拟赛恒等式：\(0+0+0+0=0\)。复盘T1好像可做。有个显然的\(n^2\)DP。推式子的时候猜到了\(\gcd=1\)的做法。进一步尝试正解未果。T2一眼只会爆搜。想到了\(b\timesb!\)的做法，应该能过\(