首页 > 编程语言 >扩展欧几里得算法与乘法逆元

扩展欧几里得算法与乘法逆元

时间：2023-05-11 11:34:58浏览次数：55  
标签：return gcd int 欧几里得 逆元 ax aligned modm 乘法

扩展欧几里得算法

基本知识

整除的基本定义与性质

定义 \(设 a,b∈Z 且 a≠0，若 b 除以 a 余数为 0 ，则称 a 整除 b ，记为 a∣b 。若 a 不能整除 b ，则称 a\nmid b 。\)

性质1 \(a∣b⟺−a∣b⟺a∣−b⟺|a|∣|b| 。\)

性质2 \(a∣b 且 b∣c⇒a∣c 。\)

性质3 \(c∣a 且 c∣b⇒c∣na+mb ，其中 n,m\in Z 。\)

性质4 $ (a+cb,b)=(a,b),其中a,b,c\in Z$

证明：

令e是a，b的公因子，可知\(e|(a+cb)\)，所以\(e\)是\(a+cb\)和\(b\)的公因子。

如果\(f\)是\(a+cb\)和\(b\)的公因子，可知\(f\)整除\((a+cb)-cb= a\)，所以\(f\)是\(a，b\)的公因子，因此\((a+cb，b)=(a，b)\)。

同余的定义与基本性质

定义 \(若整数 a,b 模 m 的余数相等，则称 a,b 模 m 同余，记作 a≡b(modm) 。若余数不等，则称 a,b 模 m 不同余，记作 a≢b(modm) 。\)

\(约定 由于对负模数 m 的讨论等价于正模数的讨论，所以若不特殊指明，我们假定模数 m>0 。\)

\(性质1（自反性） a≡a(modm) 。\)

\(性质2（对称性） a≡b(modm)⟺b≡a(modm) 。\)

\(性质3（传递性） a≡b(modm) 且 b≡c(modm)⇒a≡c(modm) 。\)

\(性质4（同加性）\)

\(a≡b(modm)⟺a±c≡b±c(modm)\)

\(a≡b(modm),c≡d(modm)⟺a±c≡b±d(modm)\)
\(性质5（同乘性）\)

\(a≡b(modm)⇒ac≡bc(modm)\)

\(a≡b(modm),c≡d(modm)⇒ac≡bd(modm)\)

\(性质6（同幂性） a≡b(modm)⇒ak≡bk(modm) ，其中 k≥0。\)

\(性质7（同除性） a≡b(modm)⇒ad≡bd(mod\frac{m}{gcd(m,d)}) ，其中 d 满足 d∣a,d∣b 。\)

\(性质8 若 a≡b(modm) ，那么 m′∣m⇒a≡b(modm′) 。\)

\(性质9\ a≡b(modm_i)(i=1,2,⋯,k)⟺a≡b(modM) ，其中 M=lcm(m_1,m_2,⋯,m_k) 。\)

\(性质10\ a≡b(modm)⇒gcd(a,m)=gcd(b,m) 。\)

辗转相除法求gcd

代码

int gcd(int a,int b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

证明

由带余除法可知,存在整数\(q, r\)使得\(a = bq + r\), \(0 ≤ r <b\), 得到\(r = a - bq\)。

显然\(gcd(a,b)=gcd(a-bq,b)=gcd(r,b)=gcd(a\%b,b)=gcd(b,a\%b)\)

时间复杂度证明

证明之前先熟悉这些知识：

1.\(m \mod n的结果在[0,n-1]之间，如果n>\frac{m}{2} ,则m \mod n的结果就是m-n\)

2.$m \mod n< \frac{m}{2} $

对2的证明：

\(记 rem为m \mod n\)

\(如果 n\leq\frac{m}{2},由1可知，r e m < n,则结论成立\)

\(如果 n>\frac{m}{2},则用1可知，rem=m-n<m-\frac{m}{2}=\frac{m}{2} ,则结论成立。\)

由2可知，在两次迭代之后，余数最多为原始值的一般。这就证明了迭代次数至多为\(2log(N)=O(logN).\)

裴蜀定理

\(如果a与b均为整数，则存在整数x和y满足ax + by = (a,b)。\)

二元一次不定方程

我们考虑如何求不定方程\(ax+by=c\)的整数解

\[我们先想一想，什么时候这个方程会有解\\ 由裴蜀定理我们可以知道\\ 如果a与b均为整数，则存在整数x和y满足ax + by = (a,b)。\\ 因此如果(a,b)\nmid c,显然方程无解\\ 如果我们已经知道了ax + by = (a,b)的解\{x,y\}\\ 那么我们就可以将x,y同时乘上\frac{c}{(a,b)}从而获得一组特解\{x_0,y_0\} \]

\[\begin{align*} &我们已知(a,b)=(b,a\%b)\\ &由题意有ax + by = (a,b)\\ &且必然存在x_1,y_1使得bx_1+(a\%b)y_1=(b,a\%b)\\ &所以ax+by=(a,b)=(b,a\%b)=bx_1+(a\%b)y_1\\ &又因为a\%b=a-\lfloor\frac{a}{b}\rfloor*b \\ &所以我们就有ax+by=bx_1+(a-\lfloor\frac{a}{b}\rfloor*b)y_1\\ \end{align*} \]

\[\begin{aligned} ax+by&=bx_1+(a-\lfloor\frac{a}{b}\rfloor*b)y_1\\ ax+by&=bx_1+ay_1-\lfloor\frac{a}{b}\rfloor*b*y_1\\ ax+by&=ay_1+b*(x_1-\lfloor\frac{a}{b}\rfloor*y_1)\\ \end{aligned} \]

\[因此如果我们解出来bx_1+(a\%b)y_1=(b,a\%b)的解\\ 那么ax + by = (a,b)的解就是 \]

\[\left\{ \begin{aligned} &x=y_1 \\ &y=x_1-\lfloor\frac{a}{b}\rfloor*y_1\\ \end{aligned} \right. \]

\[那我们什么时候会结束递归呢？\\ 显然，当我们遇到(a,b)=(b,a\%b)=(b,0)的时候我们就无法递归下去了\\ 这时候我们就需要解方程bx_n+0y_n=(b,0)=b\\ 很明显，这个方程的解是\\ \left\{ \begin{aligned} &x_n=1\\ &y_n=0\\ \end{aligned} \right.\\ 接下来我们再进行回溯之后就可以知道ax+by=(a,b)的一组解\{x,y\}了 \]

\[现在，我们已经知道了ax+by=c的一组特解\{x_0,y_0\}了\\ 我们要如何求它的通解呢\\ 我们不妨设它的通解是\\ \left\{ \begin{aligned} &x=x_0+kp\\ &y=y_0-kq\\ \end{aligned} \right.\\ 其中p,q\in N^*，k为任意整数\\ 我们想知道最小的p,q 显然，我们除了\{x_0,y_0\}以外还有一组解\{x_0+p,y_0-q\}\\ 因此我们有\\ \left\{ \begin{aligned} &ax_0+by_0=c\\ &a(x_0+p)+b(y_0-q)=c\\ \end{aligned} \right.\\ 我们用下减上就有ap-bq=0\\ 所以ap=bq\\ 我们设(a,b)=d\\ 就有a=a'd,b=b'd,(a',b')=1\\ 因此a'dp=b'dq\\ p=\frac{b'}{a'}q\\ 当p最小的时候q=a'，此时p=b'\\ 因此它的通解是\\ \left\{ \begin{aligned} &x=x_0+kb'\\ &y=y_0-ka'\\ \end{aligned} \right.\\ \]

乘法逆元

定义 \(给定整数a，且满足(a,m)=1，称ax≡1(mod\ m)的一个解为a模m的逆。\)

方法一（扩欧）

\[\begin{aligned} &am\equiv 1(mod\ b)\\ \Rightarrow &am=1+by\\ \Rightarrow &am+b(-y)=1\\ \end{aligned} \]

求出m的最小整数解即可

方法二（费马小定理）

\(设p是一个素数，a是一个正整数且p\nmid a，则a^{p-1}≡1(mod\ p)。\)

证明

所以\(a*a^{n=2}\equiv 1(mod\ p),m=a^{n-2}\)

方法三（线性递推）

显然\(inv[1]=1\)

因为\(p=i*t+r\),且\(p\equiv 0(mod\ p)\)

所以\(i*t+r\equiv 0(mod\ p)\)

两边同时乘上\(i^{-1}和r^{-1}\)

所以\(i*t*i^{-1}*r^{-1}+r*i^{-1}*r^{-1}\equiv 0(mod\ p)\)

又因为\(i*i^{-1}\equiv 1(mod\ p),r*r^{-1}\equiv 1(mod\ p)\)

就有\(t*r^{-1}+i^{-1}\equiv 0(mod\ p)\)

所以\(\lfloor\frac{p}{i}\rfloor*inv[p\%i]+inv[i]\equiv 0(mod\ p)\)

\(inv[i]\equiv -\lfloor\frac{p}{i}\rfloor*inv[p\%i](mod\ p)\)

\(inv[i]= -\lfloor\frac{p}{i}\rfloor*inv[p\%i]\%p\)

为了让\(inv[i]\)介于0到p-1，我们考虑加上\(p*inv[p\%i]\%p\)

\(inv[i]= p*inv[p\%i]\%p-\lfloor\frac{p}{i}\rfloor*inv[p\%i]\%p=(p-\lfloor\frac{p}{i}\rfloor)*inv[p\%i]\%p\)

题目

伪随机数

一个生成伪随机数的函数，seed(a+1)=[seed(a)+STEP] % MOD,为了能产生0~MOD-1的所有数,需要设定合适的 STEP和 MOD。

例如,STEP=3， MOD=5，产生0,3,1,4,2，这是正确的设定;

若STEP=15,MOD=20,只能产生0,15,10,5,这是错误的设定。

多组测试数据。

第一行，一个整数T，表示T组测试数据。1<=T<=10000。

每组测试数据输入两个数 STEP、MOD, 判断是否为正确的设定。1≤STEP,MOD<2000000000。

分析

显然\(seed(a)=a*STEP\%MOD\)

\(seed(a)+k*MOD=a*STEP\)

\(seed(a)=STEP*a-MOD*k,其中a,k\in Z\)

如果\(STEP*a-MOD*k=1\),就可以产生题目要求的所有数

由裴蜀定理，需要\((STEP,MOD)=1\)

代码

#include<bits/stdc++.h>
using namespace std;
long long t,x,y;
int main(){
	cin>>t;
	while(t--){
		cin>>x>>y;
		if(__gcd(x,y)==1)printf("yes\n");
		else printf("no\n");
	}

	return 0;
}

修塔

有编号1~n 的n个塔,除了两个塔a和b 是好的不用修以外,其他都需要重修。

james和jordan展开修塔比赛，规则是轮流修，每次可以修第j+k或j-k号塔，其中j和k是已经修好的任意两个塔，

如果不能修塔，就输了。给出n,a,b，从 james开始，问最后谁赢了。

第一行，一个整数T， 1<=T<=10000,表示有T组测试数据。

接下来T行，每行3个整数: n,a,b。2<a,b,n≤200000。a！=b。

分析

对于一座塔c，如果可以被修，显然要满足\(ax+by=c,其中x,y\in Z\)

所以对于编号为\(k(a,b)\)的塔他们都可以修

所以他们一共可以修\(\frac{n}{(a,b)}-2座塔\)

我们判断一下这个数是奇数还是偶数便可知道结果

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a,b;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&a,&b);
		int cnt=n/__gcd(a,b);
		if(cnt&1)printf("james\n");
		else printf("jordan\n");
	} 

	return 0;
}

P5656 【模板】二元一次不定方程 (exgcd)

分析

对于这一道题，我们不但要算出它的解，还要算出正整数解

因此我们要对我们所得到的特解进行一些调整

我们以求最小的正整数x为例，我们可以对x加上或减去kb'，

于是我们可以让x对b'取模但这个时候的x有可能还是为负数，因此我们就要让x再加上一个b'再取模一次

对于y，我们就可以使用\(y=(c-a*x)/b\)来计算

对于求正整数解的个数，我们先明确一点：

随着x的增大，y会不断地减小，如果对于最小的正整数解x，y都已经是负数了，那么显然没有正整数解

否则正整数解的个数就是\((x_{max}-x_{min})/b'+1\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y; 
int t,a,b,c;
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return ; 
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&a,&b,&c);
		int d=__gcd(a,b);
		if(c%d!=0){
			printf("-1\n");
			continue;
		}
		int na=a/d,nb=b/d,Plus=c/d;
		//a'x+b'y=d
		ex_gcd(na,nb);
		//ax+by=c;
		x*=Plus,y*=Plus;
		int x1,y1,x2,y2;
		
		x1=(x%nb+nb)%nb;
		y1=(c-a*x1)/b;
		if(x1==0)x1+=nb,y1-=na;
		
		y2=(y%na+na)%na;
		x2=(c-b*y2)/a;
		if(y2==0)x2-=nb,y2+=na;
		
		if(y1>0)printf("%lld %lld %lld %lld %lld\n",(x2-x1)/nb+1,x1,y2,x2,y1);
		else printf("%lld %lld\n",x1,y2);
	}
	return 0;
}

多元一次不定方程的一组解

求\(a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = c\)的一组整数解，如无整数解输出-1。

分析

考虑到\(a_1x_1+a_2x_2=(a_1,a_2)d,其中d\in Z\)

因此可以转化为求\((a_1,a_2)d+ a_3x_3 + ... + a_nx_n = c\)

以此类推

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=10;
int x,y;
int n,C[maxn],ans[maxn],A[maxn],d[maxn];
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return ;
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
void solve(int pos){
	if(pos==1){
		ans[pos]=C[pos]/d[pos];
		return ;
	}
	int a=d[pos-1],b=A[pos],c=C[pos];
	int Plus=c/d[pos];
	int na=a/d[pos],nb=b/d[pos];
	ex_gcd(na,nb);
	int nx=x*Plus,ny=y*Plus;
	ans[pos]=ny,C[pos-1]=nx*d[pos-1];
	solve(pos-1);
	return ;
}
signed main(){
	cin>>n>>C[n];
	for(int i=1;i<=n;i++){
		cin>>A[i];
		if(i==1)d[i]=A[i];
		else d[i]=__gcd(d[i-1],A[i]);
	}
	if(C[n]%d[n]!=0){
		printf("-1\n");
		return 0;
	}
	solve(n);
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}

fibo

\[\begin{aligned} &定义一个数列：\\ &f(0)=a,f(1)=b,f(n)=f(n-1)+f(n-2) ,其中a，b均为正整数，n≥2。\\ &问有多少种（a，b），使得k出现在这个数列里，且不是前两项。由于答案可能很大，你只需要输出答案模10^9+7的结果即可。\\ \end{aligned} \]

分析

实际上我们只需要解方程\(f(i-1)a+f(i)b=k\)

由于斐波那契数列的增长速度极快

所以我们大约只需要枚举30-40次

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=55,p=1e9+7;
int c,f[maxn],x,y,ans=0;
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return ;
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
signed main(){
	cin>>c;
	f[1]=1,f[2]=1;
	int pos=3;
	while(f[pos-1]+f[pos-2]<=c){
		f[pos]=f[pos-1]+f[pos-2];
		pos++;
	}
	for(int i=2;i<=pos-1;i++){
		int a=f[i-1],b=f[i];
		int d=1;
		int na=a/d,nb=b/d,Plus=c/d;
		ex_gcd(na,nb);
		x*=Plus,y*=Plus;
		int x1,y1,x2,y2;
		x1=(x%nb+nb)%nb;
		y1=(c-a*x1)/b;
		if(x1==0)x1+=nb,y1-=na;
		
		y2=(y%na+na)%na;
		x2=(c-b*y2)/a;
		if(y2==0)x2-=nb,y2+=na;
		if(y1>0)ans=(ans+(x2-x1)/nb+1)%p;
	}
	cout<<ans;

	return 0;
}

P1082 [NOIP2012 提高组] 同余方程

分析

\[\begin{aligned} &ax\equiv 1(mod\ b)\\ \Rightarrow &ax=1+by\\ \Rightarrow &ax+b(-y)=1\\ \end{aligned} \]

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,x,y;
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return ;
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
signed main(){
	cin>>a>>b;
	ex_gcd(a,b);
	x=(x%b+b)%b;
	if(x==0)x+=b;
	cout<<x<<endl;
	return 0;
}

P1516 青蛙的约会

分析

\[\begin{aligned} x+tm&\equiv y+tn(mod\ L)\\ x+tm&=y+tn+kL\\ x-y&=t(n-m)+kL\\ (n-m)t+Lk&=x-y\\ 我们令a&=n-m,b=L,c=x-y\\ 就有at+bk&=c \end{aligned} \]

这时候就会有一个问题，我们之前的a,b的系数都是正的，但是在这里我们的a,b可能为负数，这对于特解的求解会不会有影响呢

实际上并不会，我们依然可以求出正确的特解

但是我们的t显然应该是最小整数解

因此我们要对特解进行调整

问题来了，如果我们直接像原来一样进行调整，

如果我们的b'为负数，那么我们的t就会被调整为最大的负数

由于b'是负数，因此我们如果直接加上b'那t还会是一个负数

于是我们就需要特判一下，如果t是一个负数的话，b'一定也是一个负数，我们就使用t减去b'就可以获得最小的整数解

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,X,Y,N,M,L,a,b,c;
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
signed main(){
	cin>>X>>Y>>M>>N>>L;
	a=N-M,b=L,c=X-Y;
	int d=__gcd(a,b);
	if(c%d!=0){
		printf("Impossible\n");
		return 0;
	}
	int na=a/d,nb=b/d,Plus=c/d;
	ex_gcd(na,nb);
	x*=Plus,y*=Plus;
	x=(x%nb+nb)%nb;
	y=(c-a*x)/b;
	if(x<0)x-=nb,y+=na;
	cout<<x<<endl;
	return 0;
}

死循环

C语言的循环语句 for(variable=A;variable!=B;variable+=C),当 variable==B时结束循环。

A、B、C的数据类型的长度是k位，也就是说，当variable 超过k位时，只保留k位，相当于对\(2^k\)取模。

给出A、B、C和k,判断循环是否能在有限次内结束，若能结束,则输出循环次数。

如果死循环，输出"FOREVER"。

多组测试数据。

每组测试数据格式：A,B,C,k。0<A,B,C<2^k。 1<=k<32。
测试数据以 0 0 0 0 表示结束。

分析

\[\begin{aligned} A+xC&\equiv B(mod\ 2^k)\\ A+xC&=B+y*2^k\\ Cx+2^ky&=B-A\\ ax+by&=c,其中x为最小整数解\\ \end{aligned} \]

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int A,B,C,k,x,y;
int a,b,c;
void ex_gcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return ;
	}
	ex_gcd(b,a%b);
	int tmpx=x,tmpy=y;
	x=tmpy,y=tmpx-a/b*tmpy;
	return ;
}
signed main(){
	while(1){
		scanf("%lld%lld%lld%lld",&A,&B,&C,&k);
		if(A==0&&B==0&&C==0&&k==0)break;
		a=(1<<k),b=-C,c=A-B;
		int d=__gcd(a,b);
		if(c%d!=0){
			printf("FOREVER\n");
			continue;
		}
		int na=a/d,nb=b/d,nc=c/d;
		ex_gcd(na,nb);
		x*=nc,y*=nc;
		y=(y%na+na)%na;
		x=(c-b*y)/a;
		if(y<0)y-=na,x+=nb;
		printf("%lld\n",y);
	}

	return 0;
}

P3811 【模板】乘法逆元

分析

分析在上面

但是比较奇怪的是\(inv[i] = p - p / i * inv[p \% i] % p\)与\(inv[i] = (p - p / i) * inv[p \% i] % p\)在洛谷上都过了，但是在oj上第一种没过

Link

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3*1e6+5;
int n,p,inv[maxn];
signed main(){
	scanf("%lld%lld",&n,&p);
	inv[1]=1;printf("1\n");
	for(int i=2;i<=n;i++){
		inv[i]=(p-(p/i))*inv[p%i]%p;printf("%lld\n",inv[i]);
	}
	return 0;
}

A/B

分析

快速幂

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=9973;
int t,n,b; 
int poww(int num,int cnt){
	int ans=1;
	while(cnt){
		if(cnt&1)ans=ans*num%p;
		num=num*num%p;
		cnt=cnt/2;
	}
	return ans;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&b);
		printf("%lld\n",n*poww(b,p-2)%p);
	}
	return 0;
}

参考资料

数论基础

欧拉定理 & 费马小定理

数论笔记-整除

标签：return,gcd,int,欧几里得,逆元,ax,aligned,modm,乘法
From： https://www.cnblogs.com/Ayaka-T/p/17390555.html

相关文章

  • 该模型基于id=0控制 ，通过电机的基本数学模型对其定子电阻R, 永磁磁链ψf， dq轴电感Ls进
    该模型基于id=0控制，通过电机的基本数学模型对其定子电阻R,永磁磁链ψf，dq轴电感Ls进行递推最小二乘法辨识，仿真结果表明了该方法的有效性ID:8330669177527757......
  • 类欧几里得算法小记
    类欧几里得算法大概是要求这样的一个东西：给定非负整数\(a,b,c,n\)，求\(f(a,b,c,n)=\sum\limits_{i=0}^{n}{\lfloor\frac{ai+b}{c}}\rfloor\)。按道理来说整除问题一般是考虑除法分块，但是问题在于除法分块貌似适用范围是\(i\)在分母的情况。我们不妨从简单的方面入手，讨论一些......
  • 基于一阶RC模型，电池带遗忘因子递推最小二乘法+扩展卡尔曼滤波算法（FFRLS+ EKF），参数与SOC
    基于一阶RC模型，电池带遗忘因子递推最小二乘法+扩展卡尔曼滤波算法（FFRLS+EKF），参数与SOC的在线联合估计，matlab程序YID:76100659957301925......
  • 一阶RC模型自适应遗忘因子递推最小二乘法+扩展卡尔曼滤波算法AFFRLS+EKF锂电池参数和S
    一阶RC模型自适应遗忘因子递推最小二乘法+扩展卡尔曼滤波算法AFFRLS+EKF锂电池参数和SOC联合估计遗忘因子可随时间自适应变化，不再是定值，提高估计精度matlab程序参考文献ID:52100675009205808......
  • 密码工程-扩展欧几里得算法
    任务详情0.在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务1.参考《密码工程》p112伪代码实现ExtendedGCD（inta,intb,int*k,int*u,int*v）算法（52.在测试代码中计算74模167的逆。（53.自己设计至少两个测试代码。54.提交代码和运行结果截图代码实现......
  • 密码工程-扩展欧几里得算法
    密码工程-扩展欧几里得算法0.在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务1.参考《密码工程》p112伪代码实现ExtendedGCD（inta,intb,int*k,int*u,int*v）算法（52.在测试代码中计算74模167的逆。（53.自己设计至少两个测试代码。54.提交代码和运行结果......
  • 密码工程-扩展欧几里得算法
    任务详情在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务参考《密码工程》p112伪代码实现ExtendedGCD（inta,intb,int*k,int*u,int*v）算法（5在测试代码中计算74模167的逆。（5自己设计至少两个测试代码。5提交代码和运行结果截图代码代码一：#include<stdi......
  • 密码工程-扩展欧几里得算法
    密码工程-扩展欧几里得算法20201331黄文刚任务详情：0.在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务参考《密码工程》p112伪代码实现ExtendedGCD（inta,intb,int*k,int*u,int*v）算法（5在测试代码中计算74模167的逆。（5自己设计至少两个测试代码。5提交代......
  • 扩展欧几里得算法
    扩展欧几里得算法前置条件：需要掌握裴蜀定理和欧几里得算法裴蜀定理：对于不全为0的整数a,b，一定有整数x,y，使得ax+by=gcd(a,b)欧几里得算法：gcd(a,b)==gcd(b,a%b)假设有组特解x0,y0，使得ax0+by0=gcd(a,b)则必有bx1+(a%b)y1=gcd(b,a%b)=gcd(a,......
  • 最小二乘法求解线性方程组公式推导
    M行N列方程组如下。其中x,y是已知量，k是未知量：$${\left\{\begin{matrix}k_{1}x_{1,1}+k_{2}x_{1,2}+\cdots+k_{N}x_{1,N}=y_{1}\\ k_{1}x_{2,1}+k_{2}x_{2,2}+\cdots+k_{N}x_{2,N}=y_{2}\\ \vdots\\ k_{1}x_{M,1}+k_{2}x_{M,2}+\cdots+k_{N}x_{M,N}=y_{M} \end{matrix......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99