SWEA 3032. 홍준이의 숫자놀이(Python)(D3)

확장 유클리드 호제법을 이용했다.
이에 대한 내용은 별도로 작성하겠음..!

• A,B가 서로소가 아닌경우(최대공약수가 1이 아닌경우) -1 출력
  - 에라토스테네스의 체를 이용해 소수를 구해놓고 나누어 확인
• 그외의 경우 확장 유클리드 호제법 진행

ans=[]
prime_li=[1]*(10001)
for i in range(2,101):
    if prime_li[i]==1:
        for j in range(i*2,10001,i):
            prime_li[j]=0
prime_num=[i for i in range(2,10001) if prime_li[i]==1]

def coprime(a,b):
    for i in prime_num:
        if a%i==0 and b%i==0:
            return False
    return True

def gcd(a,b):
    x,y=0,1
    u,v=1,0
    while a!=0:
        q,r=b//a,b%a
        m,n=x-u*q,y-v*q
        b,a,x,y,u,v=a,r,u,v,m,n
    return str(x)+" "+str(y)
    
for m in range(int(input())):
    tmp=""
    A,B=map(int,input().split())
    if not coprime(A,B):
        print(-1)
    else:
        tmp=gcd(A,B)
    
    ans.append(tmp)
for i in range(len(ans)):
    print("#%d %s"%(i+1,ans[i]))