这个逆3x3矩阵怎么求逆矩阵？？？？？

来源：蜘蛛抓取(WebSpider) 时间：2017-11-09 05:47 标签： 矩阵的逆矩阵怎么求
求逆元[数论] - CSDN博客
求逆元[数论]
这两天都没什么东西做出来的../.T_T
第一次接触到逆元是11年大连的最后一题.囧啊，不会..什么都不会,网赛z怎么破
比如: &(8/2)%5&
我们求a*b*c*d*e*f*g..../z 前面乘积部分LL存不下所以要一边mod一边乘
最后处理到除z时，不一定能除尽
比如前面那个例子，8/5=3，3除不尽2就乘以2%5的逆元在%5
2%5的逆元=2^(5-2)=8 这是计算逆元的一种方法，后面讲。还有一直哦你方法是扩展欧几里德算法也是后面详细讲。
（3*8）%5=4=4%5
在计算(a/b)%Mod时，往往需要先计算b%Mod的逆元p（b有逆元的条件是gcd(b,Mod)==1，显然素数肯定有逆元），然后由(a*p)%Mod得结果c。这里b的逆元p满足(b*p)%Mod=1。先来简单证明一下：
(a/b)%Mod=c; & &(b*p)%Mod=1; & &==》 & (a/b)*(b*p) %Mod=c; & &==》 & &(a*p)%Mod=c;
从上面可以看出结论的正确性，当然这里b需要是a的因子。接下来就需要知道根据b和Mod，我们怎么计算逆元p了。扩展欧几里德算法，大家应该都知道，就是已知a、b，求一组解(x,y)使得a*x+b*y=1。这里求得的x即为a%b的逆元，y为b%a的逆元（想想为什么？把方程两边都模上b或a看看）。调用ExtGcd（b,Mod,x,y)，x即为b%Mod的逆元p。
&求b%Mod的逆元p还有另外一种方法，即p=b^(Mod-2)%Mod，因为b^(Mod-1)%Mod=1(这里需要Mod为素数)。
以上来自:/zhanggmcn/item/ef4dadceb4fb993e
如例子 & &3/2%5=4; 2*3%5=1 &==& &(3/2)*(2*8)%5=4 &==& (3*8)%5=4
关于扩展欧几里德:
首先扩展欧几里德主要是用来与求解线性方程相关的问题，所以我们从一个线性方程开始分析。现在假设这个线性方程为a*x+b*y=m，如果这个线性方程有解，那么一定有gcd(a,b) | m，即a，b的最大公约数能够整除m(m%gcd(a,b)==0)。证明很简单，由于a%gcd(a,b)==b%gcd(a,b)==0，所以a*x+b*y肯定能够整除gcd(a,b)，如果线性方程成立，那么就可以用m代替a*x+b*y，从而得到上面的结论，利用上面的结论就可以用来判断一个线性方程是否有解。
& & & 那么在a*x+b*y=m这个线性方程成立的情况下，如何来求解x和y呢？
& & & 1.令a1=a/gcd(a,b)，b1=b/gcd(a,b)，m1=m/gcd(a,b)。如果我们能够首先求出满足a*x1+b*y1=gcd(a,b)这个方程的x1和y1，那么x=x1*m1,y=y1*m1就可以求出来了。由欧几里德算法gcd(a,b)=gcd(b,a%b)，所以a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2，现在只要做一些变形就可以得到扩展欧几里德算法中的用到的式子了。令k=a/b(商)，r=a%b(余数)，那么a=k*b+r。所以r=a-k*b，带入上式，得到a*x1+b*y1=b*x2+(a-(a/b)*b)y2=a*y2+b*(x2-(a/b)*y2)
=& x1=y2，y1=x2-(a/b)*y2。有了这两个式子我们就知道了在用欧几里德求最大公约数的时候，相应的参数x，y的变化。现在再回过头来看一下扩展欧几里德算法的代码就很好理解了，实际上扩展欧几里德就是在求a和b的最大公约数的同时，也将满足方程a*x1+b*y1=gcd(a,b)的一组x1和y1的值求了出来。下面代码中突出的部分就是标准的欧几里德算法的代码。
__int64 exGcd(__int64 a,__int64 b,__int64 &x,__int64 &y){
__int64 g=exGcd(b,a%b,x,y);
__int64 temp=x;
y=temp-(a/b)*y;
& & &2.那么x，y的一组解就是x1*m1，y1*m1，但是由于满足方程的解无穷多个，在实际的解题中一般都会去求解x或是y的最小正数的值。以求x为例，又该如何求解呢？还是从方程入手，现在的x，y已经满足a*x+b*y=m，那么a*(x+n*b)+b*(y-n*a)=m显然也是成立的。可以得出x+n*b(n=…，-2，-1，0，1，2，…)就是方程的所有x解的集合，由于每一个x都肯定有一个y和其对应，所以在求解x的时候可以不考虑y的取值。取k使得x+k*b&0，x的最小正数值就应该是(x+k*b)%b，但是这个值真的是最小的吗？？如果我们将方程最有两边同时除以gcd(a,b)，则方程变为a1*x+b1*y=m1，同上面的分析可知，此时的最小值应该为(x+k*b1)%b1，由于b1&=b，所以这个值一定会小于等于之前的值。在实际的求解过程中一般都是用while(x&0)x+=b1来使得为正的条件满足，为了更快的退出循环，可以将b1改为b(b是b1的倍数)，并将b乘以一个倍数后再加到x上。
以上转自:http://cie./acmfan_cn/viewthread.php?tid=844
扩展欧几里德求逆元模板:
#include&iostream&
#define __int64 long long
//举例 3x+4y=1 ax+by=1
//得到一组解x0=-1，y0=1 通解为x=-1+4k,y=1-3k
inline __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)//ax+by=1返回a,b的gcd，同时求的一组满足题目的最小正整数解
__int64 ans,t;
if(b==0){x=1;y=0;}
ans=extend_gcd(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;
//(a/b)%mod=c 逆元为p，(p*b)%mod=1
//(a/b)*(p*b)%mod=c*1%mod=c
// (p*b)%mod=1 等价于 p*b-(p*b)/mod*mod=1其中要求p，b已知 等价于 ax+by=1
//其中x=p（x就是逆元）,y=p/mod,a=b,b=b*mod 那么调用extend_gcd(b,b*mod,x,y)即可求(a/b)%mod的逆元等价于a*p%mod
int main()
__int64 a,b,x,y,c,gcd,mod,p;//ax+by=c
while(cin&&a&&b&&c)
gcd=extend_gcd(a,b,x,y);
cout&&x&&&
if(c%gcd){cout&&&无解!&&&}
cout&&&x=&&&x*c/gcd&&& y=&&&y*c/gcd&&
转自：/foreverlin1204/item/5e3da7d437b4dc
根据大连I题和大神代码..再改了一个一个模板:
#include &iostream&
int x,y,void extend_Euclid(int a, int b)
extend_Euclid(b, a%b);
y = t - a/b*y;
int main()
//b%mod的逆元
while(cin&&b&&mod){
// x=0;y=0;
extend_Euclid(b,mod);
cout&&(x%mod+mod)%mod&&
本文已收录于以下专栏：
相关文章推荐
首先，通过下面的式子来看看什么是乘法逆元~x * n % P = 1，其中x和P为已知且互素，n未知（比如在 2 * n % 7 = 1 这个式子里，n就是乘法逆元）弄懂什么是乘法逆元，来看看有什么姿...
这次差不多有6道是我现在可以做的，还有一道博弈论加大数的以后再补吧，还是要多积累啊。
现在先补充两个题目的吧
CRB and Candies
Time Limit:
MS (Java/Others)    Memory Limit:
K (Java/Others)...
#define ll __int64
Link：http://acm./showproblem.php?pid=5407
CRB and Candies
Time Limit:
传送门：Happy 2004
Happy 2004
Time Limit:
MS (Java/Others)    Memory Limit:
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Sub...
内容：欧拉函数，欧拉定理，费马小定理，中国剩余定理，欧几里得定理，扩展欧几里得定理，逆元，线性筛、卡特兰数、快速幂、快速乘、矩阵乘法。欧拉函数：A={ x | 1 & =x & n...
Description　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国...
Mathematician QSCTime Limit:
MS (Java/Others)    Memory Limit: 072 K (Java/...
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)求逆矩阵_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢

我要回帖

更多关于 矩阵的逆矩阵怎么求 的文章

 

随机推荐