基本思路:
1 对于A,B,使用扩展欧几里得算法求出x,y 使Ax+By==1
2 判断正负,拼接矩阵 代码如下
n = int(raw_input().strip())
head = map(int, raw_input().strip().split())
abs_head = map(abs, head)
def gcd(a, b):
if a*b == 0:
if abs(b) == 1:
return 1, 0, b
if abs(a) == 1:
return 1, a, 0
return 0, 0, 0
if a>b:
return gcd_c(r1 = a, r2 = b, s1=1, t1=0, s2=0, t2=1)
else:
r,s,t = gcd_c(r1 = b, r2 = a, s1=1, t1=0, s2=0, t2=1)
return r, t, s
def gcd_c(r1=1, r2=1, s1=1, t1=0, s2=0, t2=1):
if r2 == 1:
return r2, s2, t2
if r2 == 0:
return r2, s2, t2
p = r1/r2
r = r1%r2
s = s1-p*s2
t = t1-p*t2
return gcd_c(r1=r2, r2=r, s1=s2, t1=t2, s2=s, t2=t)
ans = []
ans.append(head)
has_ans = 0
if n == 1:
if head[0] == 1:
print 1
has_ans = 1
else:
for i in range(1, n):
if has_ans:
break
for j in range(0, i):
r, s, t = gcd(abs_head[i], abs_head[j])
if head[i] < 0:
s = -s
if head[j] < 0:
t = -t
if r == 1:
if (i+j-1)%2==0:
s = -s
else:
t = -t
tmp = [0]*n
tmp[i] = t
tmp[j] = s
ans.append(tmp)
for z in range(0,n):
if z == i or z == j:
continue
tmp = [0]*n
tmp[z] = 1
ans.append(tmp)
mat = []
for line in ans:
line = map(str, line)
mat.append(' '.join(line))
print '\n'.join(mat)
has_ans = 1
break
if has_ans==0:
print 'No'
花了1.5小时查bug,不知道错在哪 T.T