ABC 340 F번 복기 - 확장 유클리드 알고리즘 제대로 활용하기

https://atcoder.jp/contests/abc340/tasks/abc340_f

F - S = 1

 

 

확장 유클리드 알고리즘으로 선형방정식 ax+by = 1의 해를 구하는 전형적인 문제인데...

 

어설프게 알다보니 해결하지 못했다..

 

문제탓?을 하자면 스페셜저지라는 언급을 안해주니.. 여러개 있으면 하나만 출력해도 된다는 언급을 해줘야하는데

 

그런게 없어서 헷갈리기도..

 

문제 핵심은 (x,y)가 주어질때 평면상 (0,0), (x,y), (a,b)이 이루는 삼각형의 넓이가 1이 되는 (a,b)를 구하는 문제

 

https://deepdata.tistory.com/733 

평면 상의 다각형의 넓이 구하는 신발끈 공식 구현

 

신발끈 공식으로부터 

 

0 x a 0

0 y b 0 형태로 만들 수 있고, ay - bx = 2 혹은 ay - bx = -2를 만족해야한다.

 

그러면 전형적인 확장 유클리드 알고리즘을 이용한 선형 디오판토스 방정식에서 a,b를 구하는 문제가 된다.

 

https://deepdata.tistory.com/576

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

 

 

여기서 꿀팁?은 ax + by = gcd(a,b)를 만족하는 gcd(a,b),x,y를 이전에 구현한 extended_gcd(a,b)로 구할 수 있는데

 

원하는 방정식은 ay - bx = 2나 ay - bx = -2의 형태에서 a,b를 구해야한다.

 

여기서 bx - ay = 2로 놓고 extended_gcd(x,-y)를 넣으면 gcd(x,-y),b,a를 구해준다

 

그러니까 인자로 양수가 들어가야겠지 생각하고, 예전에는 ax+by = 2로 바꿔서 해볼려고 했는데

 

무조건 양수를 넣어야한다는 생각을 할 필요는 없다

 

할수는 있지만 오히려 헷갈리기만함

 

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0

    x = 0
    y = 1

    while b != 0:
        
        q,r = a//b, a%b
        a,b = b,r

        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    return a,before_x, before_y

x,y = map(int,input().split())

g,b,a = extended_gcd(x,-y)

 

 

아무튼 x,y가 주어질때 extended_gcd(x,-y)로 bx - ay = g를 만족하는 g,b,a를 구할 수 있는데

 

원하는 값은 bx - ay = 2를 만족하는 a,b이다.

 

하지만 g가 2가 아닐 수 있다.

 

우연히 정확하게 g = 2가 된다면 그러한 a,b가 해이므로 a,b를 출력하면 끝

 

g = 2가 아니라면?

 

양변을 g로 나누고 2배하면 $$\frac{2b}{g}x - \frac{2a}{g}y = 2$$

 

핵심은 이 식이 성립해야한다. 이 식이 성립하지 않으면 정수 a,b가 존재하지 않는 것이다.

 

성립하지 않을려면? x,y가 정수이므로 a,b가 g로 나누어 떨어지지 않으면 된다. 

 

a,b가 g로 나누어 떨어진다면 식이 반드시 성립할 수 있다. 

 

그렇게 된다면 만족하는 a,b는 2a/g, 2b/g로 구해진다.

 

if abs(g) == 2:
    
    print(a,b)

else:

    if a % g != 0 or b % g != 0:
        
        print(-1)

    else:

        print(2*a//g,2*b//g)