扩展欧几里得算法的模板实现

关键词：

void exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;//gcd(a,0)显然等于1*a-0*0=a 
		return a;
	}
	int ans=exgcd(b,a%b,x,y);
	int tem=x;
	x=y;
	y-=tem-(a/b)*y;
	return ans;
}

#pragma GCC optimize("O2")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<limits.h>
#include<ctime>
#define N 100001
typedef long long ll;
const int inf=0x3fffffff;
const int maxn=2017;
using namespace std;
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch>'9'|ch<'0')
    {
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}
int exgcd(int a,int b,int &d,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;//gcd(a,0)显然等于1*a-0*0=a 
		return a;
	}
	exgcd(b,a%b,d,y,x);
	y-=a/b*x;
} 
int cal(int a,int p)
{
	int d,x,y;
	exgcd(a,p,d,x,y);
	return d==1?(x+p)%p:-1;//如果有解直接返回范围在0到p之间的解 
}
int main()
{
	int a=read(),b=read();
	printf("%d",cal(a,b));
}

void init()
{
    inv[0]=inv[1]=1;
	for(int i=2;i<mod;i++)
	inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

扩展欧几里得(模板)(代码片段)

 扩展欧几里德算法：  谁是欧几里德？自己百度去  先介绍什么叫做欧几里德算法  有两个数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 查看详情

在 Java 中使用扩展欧几里得算法实现 modInverse

】在Java中使用扩展欧几里得算法实现modInverse【英文标题】：ImplementmodInverseusingExtendedEuclidAlgorithminJava【发布时间】：2021-05-2216:34:35【问题描述】：不应使用BigInteger类的modInverse方法。我尝试并使用了这种方法，但它没有产生正确... 查看详情

模板扩展欧几里得+逆元

事实上，我们可以直接在欧几里德算法求解gcd(a,b)的过程中，构造一组ax+by=gcd(a,b)的解 这个方法依赖于递归的思想 边界：b=0时,a*1+b*0=gcd(a,b) 设我们找到了一组b*x+(a%b)*y=gcd(a,b)的解，那么： --> b*x+(a-[a/b]*b])*y=gcd... 查看详情

数论-扩展欧几里得算法

证明链接：http://blog.csdn.net/lincifer/article/details/49391175 模板：intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}   查看详情

hdu1576a/b——扩展欧几里得算法

扩展欧几里得的模板题，要记住：x=y1;y=x1-a/b*y1。这道题的推导过程如下：1.因为A/B==0，所以令A/B=x，即A=Bx。又因为n=A%m，所以m*y+n=A。由上面可推导出Bx-my=n。2.由扩展欧几里得算法可以算出B*x1+m*y1=1的根，等式两边同时乘上n可以变... 查看详情

欧几里得算法和扩展欧几里得算法

1实现代码：#include<iostream>2usingnamespacestd;34voidexgcd(longlonga,longlongb,longlong&d,longlong&x,longlong&y){5if(b==0){6d=a,x=1,y=0;7}8else{9exgcd(b,a%b,d,y,x);y-=a/b*x;10}11}1213int 查看详情

poj1061-青蛙的约会---扩展欧几里德算法求最小整数解

 扩展欧几里得算法模板#include<cstdio>#include<cstring>#definelllonglongusingnamespacestd;llextend_gcd(lla,llb,ll&x,ll&y){if(b==0){x=1,y=0;returna;}else{llr=extend_gcd(b,a%b,y,x);y-=x*(a 查看详情

扩展欧几里得算法

扩展欧几里德算法   先介绍什么叫做欧几里德算法  有两个数ab，现在，我们要求ab的最大公约数，怎么求？枚举他们的因子？不现实，当ab很大的时候，枚举显得那么的naïve，那怎么做？  欧几里德... 查看详情

欧几里得算法和扩展欧几里得算法(代码片段)

欧几里得算法基本原理和证明代码实现：#include<iostream>usingnamespacestd;intgcd(inta,intb) returnb?gcd(b,a%b):a;intmain() intx,y; cin>>x>>y; cout<<gcd(x,y)<<endl; return0;扩展欧几里得算法原理代码实现：#include<iostream>usingnamespac... 查看详情

c++中扩展欧几里得算法的递归到底发生了啥？

】c++中扩展欧几里得算法的递归到底发生了啥？【英文标题】：Whatexactlyhappensinsideextendedeuclideanalgorithm\'srecursioninc++?c++中扩展欧几里得算法的递归到底发生了什么？【发布时间】：2016-03-0906:20:53【问题描述】：我知道什么是扩展... 查看详情

[长期更新]模板&算法学习情况

...?多项式处理-高斯消元-线性基?矩阵快速幂-卡特兰数+扩展欧几里得+莫比乌斯反演*容斥-斯特林数*线性规划*中国剩余定理筛法+线性筛-杜教筛*洲阁筛计算几何?凸包& 查看详情

扩展欧几里得算法acwing877.扩展欧几里得算法——扩展欧几里得算法证明

AcWing877.扩展欧几里得算法题解与证明#include<iostream>usingnamespacestd;intexgcd(inta,intb,int&x,int&y)if(b==0)x=1,y=0;returna;int 查看详情

欧几里得算法和扩展欧几里得算法

概述欧几里德算法又称辗转相除法，用于计算两个整数(a),(b)的最大公约数。其计算原理依赖于下面的定理：(gcd)函数就是用来求((a,b))的最大公约数的。(gcd)函数的基本性质：[gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)]原理证明：(a?)可以表... 查看详情

jzyzoj1372[noi2002]荒岛野人扩展欧几里得

.../172.20.6.3/Problem_Show.asp?id=1372想法其实很好想，但是我扩展欧几里得还是用得不熟练，几乎是硬套模板，大概因为今天一个下午状态都不大好。扩展欧几里得算法计算的是:ab互质时ax+by=1或ab不互质时ax+by=gcd(a,b)（废话）的一个整数... 查看详情

扩展欧几里得算法

用途当我们已知$(a,b)$扩展欧几里得算法可以求出满足$p*a+q*b=GCD(a,b)$的$(p,q)$解集$GCD(a,b)$表示$a,b$的最大公约数 前导知识$GCD(a,b)=GCD(b,a\%b)$$GCD(a,0)=0$$a\%b=a-a/b*b$ 推导过程其实扩展欧几里得的推导过程挺自然的$p*a+q*b$$=GCD(a,b)$$=... 查看详情

扩展欧几里得算法

https://zh.wikipedia.org/wiki/扩展欧几里得算法 用类似辗转相除法，求二元一次不定方程的整数解。然后把它们改写成“余数等于”的形式//式1//式2//式3然后把它们“倒回去”//应用式3//应用式2//应用式1得解。这个过程可以用矩阵... 查看详情

数论扩展欧几里得算法

扩展欧几里得  上回刚写完欧几里得，那现在还有一个东西叫拓展欧几里得：  扩展欧几里得法是一个在求解同余方程等问题上的一个很好的方法，其具体功能如下：  在已知(a,b)时，求解一组(p,q)使得p*a+q*b=... 查看详情