|
def euc(a, b) :
x0, x1, y0, y1 = 1, 0, 0, 1
A = a
# a = bq0 + r1
# b = r1q1 + r2
# r1 = r2q2 + r3
# ...
while b != 0 :
q = a // b
r = a % b
a = b
b = r
x0, x1 = x1, x0 - q*x1
y0, y1 = y1, y0 - q*y1
if a != 1 or y0 > 10**9 :
return 'IMPOSSIBLE'
if y0 < 0 :
y0 = y0 + A
return y0
n = int(input())
for i in range(n) :
k, c = map(int, input().split())
if c == 1 :
if k < 10**9 :
print(k + 1)
else :
print('IMPOSSIBLE')
continue
if k == 1 :
print(1)
continue
print(euc(k, c))
|
확장 유클리드 호제법을 코드로 구현하는 문제이다.
ax + by = c의 정수해 (x, y)는 c가 a, b의 공약수(최대공약수였나?)가 아니라면 존재하지 않는다.
문제의 조건에서 c는 1이니 호제법을 돌리는 과정에서 gcd가 1인지 확인하고, 1이라면 그때의 정수해를 출력한다.
처음보고 아 이거 그건데 그... 하면서 머리를 싸매다가 검색하고 나면 무릎을 탁 치고 구현이 되는 상황의 반복
집나간 수학과 지식들이 머리속으로 돌아오고 있다...
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 5904 Moo 게임 (0) | 2021.11.18 |
|---|---|
| 파이썬 백준 13705 Ax+Bsin(x)=C (0) | 2021.11.17 |
| 파이썬 백준 1517 버블 소트 (0) | 2021.11.17 |
| 파이썬 백준 2749 피보나치 수 3 (0) | 2021.11.17 |
| 파이썬 백준 12846 무서운 아르바이트 (0) | 2021.11.17 |