Extended GCD

728x90

1. intro

2. code 및 분석

2.1. code

N/A

2.2. 분석

확장된 유클리드 호제법을 설명하는 문제이다.

결국

p * u + q * v = gcd(p,q)

의 공식을 만족하는 u와 v 중 최소값을 찾는 문제이다.

아래 포스팅과 같이 소스코드를 작성해보았고, 이를 적용하였다.

2023.02.02 - [Tips & theory] - Expanded Euclid's Algorithm - 확장된 유클리드 호제법.

Expanded Euclid's Algorithm - 확장된 유클리드 호제법.

서론 아직은 이걸 왜 알아야하는지 모르겠지만 일단 하는 공부 ㅋ 확장 유클리드 호제법 공식을 처음 봤을때 최소공배수인가라는 생각을 했고, 퇴근하며 운전하는 동안 머릿속으로 알고리즘을

wyv3rn.tistory.com

3. exploit

a = int(input())
a_s = a
b = int(input())
b_t = b

if a < b:
    a,b = b,a
    a_s, b_t = b,a

while 1:
    r = a % b
    if r == 0:
        GCD = b
        break
    a,b = b,r

print('GCD = ', GCD)

r = 0
s = 1
t = -1

while GCD != r:
    r = a_s * s + b_t * t
    if GCD == r:
        break
    if r > 0:
        t -= 1
    else:
        s += 1

print('s = ',s,'t = ',t)

r = 0
s = -1
t = 1

while GCD != r:
    r = a_s * s + b_t * t
    if GCD == r:
        break
    if r < 0:
        t += 1
    else:
        s -= 1

print('s = ',s,'t = ',t)

┌[wyv3rn🐲]-(/mnt/c/hacking)
└> python3 solve.py
32321
26513
GCD =  1
s =  18109 t =  -22076
s =  -8404 t =  10245