关键词：
扩欧求逆元~~
若有$a$和$x$满足$ax≡1(mod p)$，则称$a$和$x$是在模$p$意义下的乘法逆元，此时在模$p$意义下乘以$x$相当于除以$x$。
一个数有逆元的充要条件是$gcd(a,p)=1$，此时逆元唯一存在。
给定$p$，要求$a$的逆元，相当于求解同余方程$ax≡1(mod p)$；
容易转化为求解方程$ax-py=1$。
所以就可以用解二元一次方程的解法，解出一组的解$x_0$，$y_0$，然后检验$gcd(a,p)$是否为1；
注意到当$p$为质数的时候可以省略这一步；
然后调整$x_0$到$0...m-1$的范围中就行了。
没了？
时间复杂度$O(nlogn)$
代码：
1 //求mod998244353意义下的逆元 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define mod 998244353 7 using namespace std; 8 typedef long long ll; 9 ll a; 10 ll exgcd(ll a,ll b,ll &d,ll &x,ll &y) 11 if(!b) 12 d=a; 13 x=1; 14 y=0; 15 else 16 exgcd(b,a%b,d,y,x); 17 y-=x*(a/b); 18 19 20 ll getinv(int a,int p) 21 ll d,x,y; 22 exgcd(a,p,d,x,y); 23 return (x+p)%p; 24 25 int main() 26 scanf("%lld",&a); 27 printf("%lld",getinv(a,mod)); 28 return 0; 29
扩展欧几里得算法(代码片段)
代码：1longlonge_gcd(longlonga,longlongb,longlong&x,longlong&y)23if(b==0)45x=1,y=0;6returna;78longlongans=e_gcd(b,a%b,x,y);9longlongtmp=x;10x=y;11y=tmp-a/b*y;12returnans;131)扩展欧几里得算法求ax 查看详情
欧几里得，扩展欧几里得（模板）(代码片段)
1intgcd(inta,intb)23returnb?gcd(b,a%b):a;//最后返回的a为最大公约数4 扩展欧几里得求逆元：51nod12561#include<iostream>2#include<stdio.h>3#include<string.h>4usingnamespacestd;5intd,x,y;6//ax+by=1(x为a 查看详情
扩展欧几里得(代码片段)
首先接触的就是欧几里得求最大公约数（GCD）1intgcd(inta,intb)2//b<a3while(b)4intt=a%b;5a=b;6b=t;78returna;9递归的写法：1intgcd(inta,intb)2if(!b)returna;3returngcd(b,a%b);4 在扩展欧几里得中，设法求ax+by=gcd(a,b)中的一组x和y的解当b=0的时 查看详情
关于扩展欧几里得(代码片段)
给出两个整数a,b扩展欧几里得可以求出gcd(a,b)，并且能顺带算出一组特解(x,y)，使ax+by=gcd(a,b)。其实扩展欧几里得算法就是收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。原理如下：设a=r0，b=r1，那么根据... 查看详情
扩展欧几里得(模板)(代码片段)
扩展欧几里德算法： 谁是欧几里德？自己百度去 先介绍什么叫做欧几里德算法 有两个数ab，现在，我们要求ab的最大公约数，怎么求？枚举他们的因子？不现实，当ab很大的时候，枚举显得那么的na&... 查看详情
[模板]欧几里得算法/扩展欧几里得(代码片段)
最大公因数（欧几里得算法）$gcd(a,b)=gcd(b\%a,a)$（不一定需要a<b）$gcd(0,b)=b$1inlineintgcd(inta,intb)2returna==0?b:gcd(b%a,a);3扩展欧几里得寻找$ax+by=gcd(a,b)$的一组解x,y（一定存在整数解）$ax+by=gcd(a,b)=gcd(b\%a,a)=(b-lfloorfracba 查看详情
hdu2669romantic扩展欧几里得(模板题)(代码片段)
<题目链接>题目大意：Nowtellyoutwononnegativeintegeraandb.FindthenonnegativeintegerXandintegerYtosatisfyX*a+Y*b=1.Ifnosuchanswerprint"sorry"instead. InputTheinputcontainsmultipletestcases. Eachc 查看详情
扩展欧几里得算法详解(代码片段)
本篇将附上扩展欧几里得算法的思想与推导;对于一个方程(a*x+b*y=gcd(a,b))来说,我们可以做如下的推导:设有(a*x_1+b*y_1=gcd(a,b));同时我们有(b*x_2+(a\%b)*y_2=gcd(b,a\%b));对于这个方程组,我们希望知道的是(x_1,x_2,y_1,y_2)之间的关系,这样我们... 查看详情
扩展欧几里得及中国剩余定理(代码片段)
Exgcd扩展欧几里得voidexgcd(inta,intb,int&x,int&y)if(!b)x=1,y=0;return;exgcd(b,a%b,x,y);b-=y*(a/b);对于(gcd(a,b)=g)，(a imesk_1+b imesk_2=g)通过(exgcd(a,b,x,y))(k_1=x+k imesb)对于(gcd(a,b)=g 查看详情
exgcd（扩展欧几里得算法）(代码片段)
定理，证明，少例题其实挺简单。GCD（辗转相除法）定理：\\[\\gcd(a,b)=\\gcd(b,a\\%b)\\]证明：\\[\\text设a=kb+r\\text，则r=a\\bmodb\\]\\[\\text若c\\text是a,b\\text的一个公约数，则c\\mida,c\\midb\\]\\[\\becauser=a-kb\\]\\[\\thereforec\\midr\\]\\[ 查看详情
扩展的欧几里得算法(代码片段)
求解形如ax+by=gcd(a,b)的一组解。#include<bits/stdc++.h>//ax+by=gcd(a,b)x=?y=?usingnamespacestd;intextend_gcd(inta,intb,int&x,int&y)intret,tmp;if(!b)x=1;y=0;returna;ret=extend_gcd(b,a%b,x,y);tm 查看详情
hdu2669romantic(扩展欧几里得定理)(代码片段)
...得a*x+b*y=1，如果找不出输出sorry 题解：显然是用扩展欧几里得定理求解。又扩展欧几里得定理有，如果a*x+b*y=d 要使得方程有解必有gcd(a,b)为d的约数。而此题的d=1 所以若gcd(a,b)!=1，则应该输出sorry #include<bits/s... 查看详情
扩展欧几里得推导及应用(代码片段)
ax+by=gcd(a,b)求解简单推导假设有$ax_1+by_1=gcd(a,b)$成立由欧几里得算法知$gcd(a,b)=gcd(b,a$%$b)$又有$bx_2+(a$%$b)y_2=gcd(b,a$%$b)$合并得$ax_1+by_1=bx_2+(a$%$b)y_2$$a$%$b=a-\lfloora/b\rfloorb$带入上式得$ax_1+by_1 查看详情
hdu-2669romantic---扩展欧几里得(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2669题目大意：给定ab，求ax+by=1是否有解，输出x为正数的最小的解解题思路：ab互质才有解，下面的方法可求出最小正数的x的解1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4llextgc... 查看详情
扩展欧几里得与乘法逆元(代码片段)
一。欧几里得算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。递归实现：1intgcd(inta,intb)23if(b==0)4returna;5return6gcd(b,a%b);7优... 查看详情
扩展欧几里得算法（exgcd）(代码片段)
...在一对整数x，y满足：a*x+b*y=gcd（a，b）证明如下： 在欧几里得算法的最后一步：b=0，即：gcd（a，0）=a对于b>0，根据欧几里得算法gcd（a，b）=gcd（b，a%b）。假设存在一对x，y满足：b*x+（a%b）*y=gcd（b，a%b）因为b*x+（a%b）*y=b*... 查看详情
扩展欧几里得(exgcd)与同余详解(代码片段)
exgcd入门以及同余基础gcd，欧几里得的智慧结晶，信息竞赛的重要算法，数论的...（编不下去了讲exgcd之前，我们先普及一下同余的性质：若，那么若，，且p1，p2互质， 有了这三个式子，就不用怕在计算时溢出了。下面我会... 查看详情
扩展欧几里德算法(代码片段)
0、欧几里德定理一切的基础，自然就是欧几里德定理了。它的形式非常简单（sometimesnaive）gcd(a,b)=gcd(b,amodb) 证明：假设a,b的公约数为g,且$$a=bx+y(x,yinZ)$$则显然有$$gmida,qquadgmidb,qquadamodb=y$$$$ecau 查看详情