🧚‍♂️알고리즘🧚‍♂️ - 정수론2(유클리드 호제법)

🔢유클리드 호제법🔢

두 수의 최대공약수 gcd()를 구하는 알고리즘 

🍀기본 방법	소인수 분해를 이용 /  공통된 소수들의 곱 구하기
🍀유클리드 호제법	1 ) 큰 수를 작은 수로 나누는 MOD 연산 수행 2 ) 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD 연산 수행 3 ) 단계 2를 반복하다가 MOD 값이 0이 되는 순간의 작은 수가 최대공약수

+ MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 (%)

+ 최소공배수 : 두 수의 곱을 최대공약수로 나누면 됨

 

최대공약수/ 최소공배수 구하는 보편적 코드

# 최대공약수
def gcd(n, m):
    for i in range(min(n,m),0,-1): 
        if n%i ==0 and m%i==0:
            return i
      

# 최소공배수
def lcd(n, m):
    for i in range(max(n,m),n*m+1)
        if i%n == 0 and i%m == 0:
            return i

---

🥉브론즈 1

1934번: 최소공배수

+ 최소공배수 : 두 수의 곱을 최대공약수로 나누면 됨

from sys import stdin
t = int(stdin.readline())

def Euclidean(a, b) :
    fir = max(a,b)
    sec = min(a,b)
    if fir % sec == 0:
        global result
        result = sec
    else:
        Euclidean(sec,fir % sec)

for _ in range(t):
    a, b  = map(int, stdin.readline().split())
    result = 0
    Euclidean(a,b)
    print(int(a*b /result))

더 현명한 함수

def Euclidean(a, b) :
    if b == 0:
        return a
    else:
        return Euclidean(b, a % b)

재귀랑 return..

return 한 값은 한 함수 전까지만 전달되므로 재귀 여러번 됐을 때 결과만 리턴하면 none 리턴되지만

결과일 때 말고의 함수에서 다음 함수 리턴하면 시작점(초기리턴) 까지 결과값이 도착한다!

 

글로벌 그만 쓰기..

 

그리고 놀랍게도 아래 거 작은수 큰수 거꾸로 들어가도 

한번 돌면 제대로 들어가므로

신경써줄 필요 없다.! wow

---

🥈실버 1

1850번: 최대공약수

규칙 찾기!!

- "수의 길이"를 나타내는 입력값 두 개의 최대 공약수는 "실제 수의 최대공약수"의 길이를 나타낸다 !!

 

따라서 입력값의 최대공약수를 구한 뒤 그 수만큼 1을 출력하면 됨.

from sys import stdin

def Euclidean(a, b) :
    if b == 0:
        return a
    else:
        return Euclidean(b, a % b)


a, b  = map(int, stdin.readline().split())
result = Euclidean(a,b)

for _ in range(result):
    print(1, end ='')

---

🥇골드 2

1033번: 칵테일

- 사이클이 없는 트리 구조 + DFS 이용

 

모든 비율의 최소공배수를 다 곱한 무지막지한 기준 수를 만들고

그 수를 임의의 노드에 배치

 

그 임의의 노드부터 인접 리스트 이용해서 DFS 수행하기

이전 노드와의 비율을 계산해서 대입

기준 수에 비례하는 수들로 전부 설정 완료

(비율 전부 1:1로, 정수로 맞춰짐)

 

"최소 질량"이라는 조건 있으므로

모든 노드를 돌며 최대공약수 갱신해서

모든 값 최대공약수로 나눠서 출력

from sys import stdin
N = int(stdin.readline())
#인접리스트
near = [[] for _ in range(N)]
#방문체크
visit = [False for _ in range(N)]
# 값저장
result = [0 for _ in range(N)]

#최대공약수
def gcd(a, b) :
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
#기준 수
num = 1
#인접리스트저장
for i in range(N-1):
    a, b, p, q = map(int, stdin.readline().split())
    near[a].append([b,p,q])
    near[b].append([a,q,p]) #거꾸로주의
    num *= (p*q) // gcd(p,q) #최소공배수 곱해서 기준 수 만들기 
    
#탐색하며 비율 1:1 갱신  
def DFS(v):
    visit[v]= True
    for cha in near[v]:
        nextV = cha[0]
        if not visit[nextV]:
            result[nextV] = result[v] * cha[2] // cha[1]
            DFS(nextV)

#임의의 노드에 기준 수 배치
result[0] = num
DFS(0)

#현재 질량들의 최대공약수 구하기
reGcd = result[0]
for i in range(N):
    reGcd = gcd(reGcd, result[i])

#최소 질량으로 출력
for i in range(N):
    print(result[i] // reGcd , end=' ')

 

---

🔢확장 유클리드 호제법🔢

 #유클리드 호제법의 목적 : 최대공약수 구하기

확장 유클리드 호제법의 목적 : 방정식의 해 구하기

 

ax + by = c (a,b,c, x, y 는 정수)

c % gcd(a,b) = 0 인 경우에만 정수해를 가짐

=> c가 a,b의 최대공약수의 배수인 경우에만 정수해를 가짐

=>  ax + by = c가 정수해를 가지게 하는 c의 최솟값이 gcd(a,b)임

 

확장 유클리드 호제법

으악

어려운데요..

튀튀

---

🥇골드 1

이었던? 현재 채점 준비 중

 

21568번: Ax+By=C

a, b, c = map(int, input().split())

def ged(a, b) :
    if b == 0:
        return a
    else:
        return ged(b, a % b)
    
def Execute(a, b):
    ret = [0] * 2 
    if b == 0:
        ret[0] = 1
        ret[1] = 0
        return ret
    q = a // b
    V = Execute (b, a % b)
    ret[0] = V[1]
    ret[1] = V[0] - V[1] * q
    return ret

mgcd = ged(a, b)

if c % mgcd != 0:
    print(-1)
else:
    mok = int(c / mgcd)
    ret = Execute(a, b)
    print (ret[0] * mok, end=' ')
    print(ret[1] * mok)