编程练习赛16 D 矩阵游戏 python 一直在WA 求查BUG

0
0

基本思路:

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'

0 answer(s)

write answer 切换为英文 切换为中文


转发分享