A.ModuloRuinstheLegend\(题目即求（sum+n*s+(n+1)*n/2*d）\equiv\modm的最小值\)\(由裴蜀定理可得n*s+(n+1)*n/2*d=gcd(n,(n+1)*n/2)\)\(令p=gcd(n,n*(n+1)/2)\)\(可以表示为(sum+k*p+t*m)\equiv\modm\)\(令g=gcd(p,m)\)\((sum+g*z)%m\)\(sum+g*z>=m时存在最小值\)\(

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

扩展欧几里得算法（Exgcd）裴蜀定理对于任意一组整数\(a,b\)，存在一组整数\(x,y\)，满足\(ax+by=\gcd(a,b)\)。Proof：考虑数学归纳法。当\(b=0\)时，由于\(\gcd(a,0)=a\)，则对于\(ax+0y=a\)这个不定方程，\(x=1\)，\(y\)取任意整数。假设存在一组整数\(x,y\)，满足$bx+(a\bmodb)y

CSP-Srp+++++++++++ǰ����ʾ,��ƪ���´���ע��~��ѧ������intksm(inta,intb,intp){intret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b=b>>1;}returnret;}//b��λö�������λΪ1�������aÿ��a�˷�Lucasint

\(非常简单的一道板子训练题\)\(对于问题一：直接使用快速幂解决\)\(对于问题二：使用exgcd解决\)\(对于问题三：使用bsgs解决\)\(code:\)点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()#definerall(x)x.rbegin(),x.rend()#d

扩展欧几里得算法（exgcd)详解线性同余方程使用\(exgcd\)解决，详解看这里本质上就是同余方程转化为二元一次不定方程，用\(exgcd\)来解。乘法逆元可以用来干很多事。首先，分数取模这个很常见的东西就用的是乘法逆元。\(b\)模\(p\)意义下的逆元\(b^{-1}=b^{p-2}(mod\p)\)所以\(

欧几里得算法费马小定理当a,p都是是质数时,a^(p-1)=1(modp)证明：举个例子a=2,p=5;1,2,3,4集合（1）{1，2，3，4...,(p-1)}2,4,6,8=>%5=>2,4,1,3集合（2）{1a%p,2a%p,3a%p,4a%p...,(p-1)a%p}我们发现{1，2，3，4}和{2，4，1，3}只是位置不同，成积相同怎么个一定乘积相

Exgcd学习笔记引理Bézout'stheorem对于\(gcd(a,b)=d\)的情况，一定\(\existsx,y\)，使得\(ax+by=d\)成立。相反的，当解方程\(ax+by=c\)时，若\(c\)不是\(d\)的倍数，那么此方程一定无解。Exgcd推导我们知道如何通过辗转相除法求出\(gcd(a,b)\)，那么结合贝祖定理，不难

Exgcd和Excrt的一些推导ExgcdExgcd是用来求解二元一次不定方程的算法，即\[ax+by=c\]根据贝祖定理，该方程有解当且仅当\(\gcd(a,b)\midc\)，所以只用求解\[ax+by=\gcd(a,b)\]又因为\[\gcd(a,b)=\gcd(b,a\bmodb)\]可以先求解\[bx'+(a\bmodb)y'=\gcd(a,b)\]变形得\[

一道简单的数学题～首先分析题意。精简得出：假设跳了\(t\)次，那么青蛙A的坐标是\((x+mt)\modL\)，青蛙B的坐标是\((y+nt)\modL\)，列出方程：\[x+mt\equivy+nt\pmodL\]由于余数具有可减性，所以把\(y+nt\)移到左边，得出：\[x-y+mt-nt\equiv0\pmodL\]写成人话：\[(x-y+mt-nt)\mod

线性丢番图方程定理设\(a,b\)是整数且\(gcd(a,b)=d\).如果\(d\)不能整除\(c\),那么方程\(ax+by=c\)没有整数解,如果\(d\)可以整除\(c\),则存在无穷个解.另外,如果\((x_0,y_0)\)是方程的一个特解,那么所有解都可以表示为:\[x=x_0+(\frac{b}{d})n,y

欧拉定理：若正整数\(a,n\)互质，则\(a^{\varphi(p)}\equiv1(\bmodp)\)推论（扩展欧拉定理）：\[a^b\equiv\begin{cases}a^{b\\bmod\\varphi(p)}\\\\\\\\\\gcd(a,p)=1\\a^b\\\\\\\\\\\\\\\\\\\\\\gcd(a,p)!

扩展欧几里得算法（Exgcd）裴蜀定理对于任意一组整数\(a,b\)，存在一组整数\(x,y\)，满足\(ax+by=\gcd(a,b)\)。Proof：考虑数学归纳法。当\(b=0\)时，由于\(\gcd(a,0)=a\)，则对于\(ax+0y=a\)这个不定方程，\(x=1\)，\(y\)取任意整数。假设存在一组整数\(x,y\)，满足$bx+(a\bmodb)y

试求方程\(ax+by=\gcd(a,b)\)的一组整数解,其中\(a\)和\(b\)是给定的数提前准备好一个式子:辗转相除法\[\gcd(a,b)=\gcd(b,a\bmodb)\]同时我们可以注意到，\(\bmod\)的等价版本:\[a\bmodb=a-b\lfloor\frac{a}{b}\rfloor\]开始推式子首先考虑\(b=0\)的情况，因为

裴蜀定理对于任意整数\(a,b\)都存在整数\(x,y\)，使得\(ax+by=gcd(a,b)\)扩展欧几里得算法（exgcd)设整数\(a,b,x,y\)满足\(ax+by=gcd(a,b)\)若\(b=0\)，则\(x=1\)，\(y\)取任意整数若\(b>0\)\[ax+by=gcd(a,b)\]\[=gcd(b,a\mod\b)\]\[=bx_0+(a\mod\b)y_0\]\[=bx_0+(a-

欧几里得算法(exgcd)简介用于求解\(ax+by=gcd(a,b)\)，在求\(gcd\)的过程中进行求解。原理由辗转相除法的过程我们可以得到：\[ax_1+by_1=gcd(a,b)\\bx_2+(a\bmodb)y_2=gcd(b,a\bmodb)\\由欧几里得定理可知：gcd(a,b)=gcd(b,a\bmodb)\\所以ax_1+by_1=bx_2+(a\bmodb)y_2

扩展欧几里得算法（ExtendedEuclideanalgorithm,EXGCD），常用于求\(ax+by=c\)的一组可行解。过程设\(ax_1+by_1=\gcd(a,b)\)\(bx_2+(a\modb)y_2=gcd(b,a\modb)\)由欧几里得算法:\(\gcd(a,b)=gcd(b,a\modb)\)所以：\(ax_1+by_1=bx_2+(a\modb)y_2\)又因为:\(a\mod

你说得对，我也不知道怎么整合到数数论论里。\((a,b)=1\)是\(ax\equiv1(\bmodb)\)有解的充要条件。首先，对于\(x=0\rightarrowb-1\)，\(ax\equivy(\bmodb)\)，\(y\)互不相同。证明考虑加加减减。考虑求出这个解，得到\(ax=by+1\)。不难有推论：若\((a,b)=1\)，\(ax+by=1\)有

877.扩展欧几里得算法-AcWing题库878.线性同余方程-AcWing题库#include<bits/stdc++.h>usingnamespacestd;intexgcd(inta,intb,int&x,int&y){if(!b){x=1,y=0;returna;}else{intt=exgcd(b,a%b,y,x);

rank2还需努力7paoxiaomo不爱DP很简单的一道DP赛时看错数据范围导致陷入思考误区其实只用求每个前缀和对应的答案然后往后合并区间一但有区间和等于pre[i]那么将该区间加入并且计算贡献如果区间和大于pre[i]那么该答案不符合点击查看代码#include<bits/stdc++.h>#de

数学、数论namespacemath{ intmu[MAXN],prime[MAXN]; bitset<MAXN>is_prime; intMOD; intfrac[MAXN]; intqpow(inta,intb){ if(b==0)return1; if(b==1)returna; intk=qpow(a,b>>1); k*=k;k%=MOD; if(b&1)k*=a;k%=MOD; returnk;

可能不全，老文章在这什么是通解，我们知道二元一次方程，是如果只有一个式子，那么解会有无数个，而通解就是指让我们只找到一个解就可以推出其他所有解的式子。注意以下变量都为整数。知道了定义下面就是推式子了，首先设\(x,y\)是\(ax+by=\gcd(a,b)\)的一个解，那么有\[y=\le

重新整理一下扩欧。扩展欧几里得就是欧几里得算法也就是辗转相除法的扩展应用，扩展后的作用主要为求二元一次方程组的一个解。基本原理众所周知，一个式子是无法确定两个未知数的唯一值的，因此exgcd只能解出一种符合要求的解，但是因为有通解的存在，你可以由这个解推出其他所有的可

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

P5656【模板】二元一次不定方程(exgcd)若存在\(ax+by=c\)，则可以根据特解\(x,y\)求出任意通解\(x',y'\)：\(\begin{cases}x'=x+k*\frac{b}{\gcd(a,b)}\\y'=y-k*\frac{a}{\gcd(a,b)}\end{cases}(k\in\mathbb{Z})\)求特解的方法是「扩展欧几里得（exgcd）」，如果没接触过可以先阅读