/*
求行列式 O(n^3)
*/
# include
<
string
.h
>
int
v[N][N], t[N];
int
gcd(
int
a,
int
b) {
return
b
?
gcd(b, a
%
b):a;}
int
det(
int
n)
{
int
c, r, i;
int
cof
=
1
, ret
=
1
;
int
mc, mh;
for
(c
=
1
; c
<=
n;
++
c)
{
for
(r
=
c; r
<=
n;
++
r)
{
if
(v[r][c]
<
0
)
for
(i
=
c; i
<=
n;
++
i) v[r][i]
=
-
v[r][i];
for
(tt
=
0
, i
=
c; i
<=
n;
++
i)
if
(v[r][i]
!=
0
)
if
(tt
==
0
) tt
=
v[r][i];
else
tt
=
gcd(v[r][i], tt);
if
(tt
<
0
) tt
=
-
tt;
if
(tt
>
1
)
for
(i
=
c; i
<=
n;
++
i) v[r][i]
/=
tt;
}
for
(mv
=
v[
1
][c], mr
=
c, r
=
c
+
1
; r
<=
n;
++
r)
{
if
(v[r][c]
<
0
)
for
(ret
=
-
ret, i
=
c; i
<=
n;
++
i) v[r][i]
*=
-
1
;
if
(v[r][c]
>
mv) mv
=
m[r][c], mr
=
r;
}
/*
行列式整列都为 0
*/
if
(mv
==
0
)
return
0
;
/*
交换行使 v[c][c] 是 v[c
n][c] 中最大的
*/
memcpy(t
+
1
, v[
1
]
+
1
,
sizeof
(v[
0
][
0
])
*
n);
memcpy(v[
1
]
+
1
, v[mr]
+
1
,
sizeof
(v[
0
][
0
])
*
n);
memcpy(v[mr]
+
1
, t
+
1
,
sizeof
(v[
0
][
0
])
*
n);
/*
消去 c+1..n 行行首非零元素
*/
for
(r
=
c
+
1
; r
<=
n;
++
r)
if
(v[r][c])
{
mh
=
v[r][c]
/
gcd(mv, v[r][c]));
mc
=
mv
*
mh
/
v[r][c];
for
(t
=
c; t
<=
n;
++
c) v[r][t]
=
mc
*
v[r][t]
-
mh
*
v[c][t];
cof
*=
mc;
}
ret
*=
v[c][c];
}
return
ret
*
mc;
}
posted on 2012-08-30 17:20
yajunw 阅读(359)
评论(0) 编辑 收藏 引用