[Python] 정수론

# 7-1. 소수 구하기

• 전에 정리했지만 소수를 구하는 대표적인 판별법으로 에라토스테네스의 체가 있다.
  • 주어진 범위의 수 리스트를 생성한다.
  • 1은 소수가 아니므로 삭제 하고, 리스트 2부터 시작한다.
  • 선택한 수의 배수를 모두 삭제한다.
  • 이미 지운 수는 다시 지우지 않고, 지워지지 않은 수를 선택하며 리스트의 끝까지 반봇한다.
  • 이중 for문이지만 실제 시간 복잡도는 배수 삭제 연산으로 바깥쪽 for문을 생략하는 경우가 많아 O(Nlog(logN))이다.
  • 또한 N = a*b일때, a와 b는 N의 제곱근보다 클 수 없으므로 탐색은 N의 제곱근까지만 탐색한다.

 

https://www.acmicpc.net/problem/1929

import math
M, N = map(int, input().split())
A = [0]*(N+1)

for i in range(2, N+1):
    A[i]=i # 수 리스트 초기화

for i in range(2, int(math.sqrt(N))+1): # 제곱근까지만 수행
    if A[i]==0:
        continue
    for j in range(i+i, N+1, i): # 배수 지우기
        A[j]=0 # 현재 수가 소수가 아님을 표시

for i in range(M, N+1):
    if A[i] != 0:
        print(A[i]) # 소수인 값 출력

 

 

https://www.acmicpc.net/problem/1456

import math
Min, Max = map(int, input().split())
A = [0]*10000001

for i in range(2, len(A)):
    A[i]=i 

for i in range(2, int(math.sqrt(len(A))+1)): # 제곱근까지만 수행
    if A[i]==0:
        continue
    for j in range(i+i, len(A), i): # 배수 지우기
        A[j]=0

count = 0

for i in range(2, 10000001):
    if A[i]!=0: # 소수인 경우
        temp = A[i]
        while A[i]<=Max/temp: # 변수 표현 범위를 넘어갈 수 있어 이항 정리로 처리
            if A[i]>=Min/temp: # 실제로는 A[i]*temp >= Min
                count +=1
            temp = temp*A[i]

print(count)

• 먼저 에라토스테네스의 체를 이용해 입력범위(10^14) 내의 소수를 모두 구한다.
• 이후 주어진 소수들의 N 제곱값이 A~B 범위 내에 존재하는지 판별하여 개수를 센다.
• B와의 비교를 위해 N을 제곱한 값이 변수 표현 범위를 초과할 수 있다. 이때 오류 방지를 위해 소수 N과 B/N^(k-1)을 비교한다.

 

https://www.acmicpc.net/problem/1747

import math
N= int(input())
A = [0]*10000001

for i in range(2, len(A)):
    A[i]=i

for i in range(2, int(math.sqrt(len(A))+1)): # 제곱근까지만 수행
    if A[i]==0:
        continue
    for j in range(i+i, len(A), i): # 배수 지우기
        A[j]=0

def isPalindrome(target): # 팰린드롬 수 판별 함수
    temp = list(str(target))
    s = 0
    e = len(temp)-1
    while(s<e):
        if temp[s]!=temp[e]:
            return False
        s+=1
        e-=1
    return True

i=N

while True: # N부터 1씩 증가시키면서 소수와 팰린드롬 수가 맞는지 판별
    if A[i]!=0:
        result = A[i]
        if isPalindrome(result): # 첫 팰린드롬이자 소수인 수가 나오면 종료
            print(result)
            break
    i+=1

• 먼저 최대 범위에 해당하는 모든 소수를 구한다.
• 구한 소수 리스트에서 N보다 크거나 같으면서 팰린드롬인 수를 찾아낸다.
• 팰린드롬 수 판별 시 숫자를 리스트 형태로 변환하면 편리하게 구현 가능하다.

 

https://www.acmicpc.net/problem/1016

import math
Min, Max = map(int, input().split())
Check = [False]*(Max-Min+1)

for i in range(2, int(math.sqrt(Max)+1)):
    pow = i*i # 제곱수
    start_index = int(Min/pow)
    if Min%pow != 0:
        # 나머지가 있는 경우 1을 더해 Min보다 큰 제곱수에서 시작하도록 설정
        start_index += 1
    for j in range(start_index, int(Max/pow)+1):  # 제곱수의 배수 형태로 탐색
        # j*pow가 Max보다 작으면 제곱수를 True로 변경
        # int((j*pow))-Min 값이 제곱수에 해당하는 값의 인덱스이다.
        Check[int((j*pow)-Min)]=True

count = 0

for i in range(0, Max - Min+1):
    if not Check[i]:
        count += 1

print(count)

• 에라토스테네스의 체 알고리즘 방식을 제곱수 판별 로직에 적용해야 하는 문제.
• 먼저 2의 제곱수인 4부터 max값까지 제곱수를 찾는다.
• 이후 탐색한 리스트에서 제곱수로 확인되지 않은 수의 개수를 센 후 출력한다.

 

---

# 7-2. 오일러 피

• 오일러 피 함수 P[N]는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.
  • 먼저 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스 값으로 초기화한다.
  • 2부터 시작하여 현재 리시트의 값과 인덱스가 같으면(소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] =P[i] - P[i]/K 연산을 수행한다. (i는 K의 배수)
  • 예를 들어, 리스트 생성 후 2를 선택했다면 2의 모든 배수마다(2포함) P[i] = P[i] - P[i]/2 연산을 수행한다. P[4] = P[4] - P[4]/2 = 2, P[6] = P[6] - P[6]/2 = 3, ...
  • 리스트 끝까지 위 과정을 반복하여 오일러 피 함수를 완성한다.
• 수학적 원리
  • 처음 초기화된 리스트는 서로소가 될 수 있는 후보의 개수이다. 즉, 6이라면 후보(1,2,3,4,5,6)으로 6 값을 가진다.
  • 다음 리스트의 처음부터 탐색하면서 2의 배수인 수들이 탈락하며 P[6] = 3이 된다.(후보 1,3,5)
  • 다음으로 3의 배수인 수들이 탈락하여 P[6] = 2가 된다. 후보(1, 5)
  • 3과 2의 공배수, 즉 중복 삭제를 막기 위해 지속적으로 업데이트를 하고, 업데이트한 값을 기준으로 연산식을 수행해야 한다.

 

https://www.acmicpc.net/problem/11689

import math
N = int(input()) # 소인수 표현
result = N # 결과값

for p in range(2, int(math.sqrt(N))+1): # 제곱근까지만 진행
    if N%p == 0: # p가 N의 소인수이면
        result -= result/p # 결과값 업데이트(오일러 피 함수)
        while N%p==0:
            # 2^7*11이라면 2^7을 없애고 11만 남김
            N/=p

if N>1: # 반복문에서 제곱근까지만 탐색했으므로 1개의 소인수가 누락되는 케이스 처리
    # 즉, n이 1보다 크면 n이 마지막 소인수라는 뜻이다. 따라서 마지막으로 업데이트
    result -= result/N
    
print(int(result))

• GCD(n,k) = 1, 즉 n과 k가 서로소인(최대공약수가 1이므로!) 값의 개수를 구한다.
• 처음 result값은 N으로 초기화 하고, 오일러 피 함수를 통해 서로소가 아닌 수가 있다면(N%p==0) 소인수를 제거한다.
• 마지막 소인수까지 제거해준다.

 

---

# 7-3. 유클리드 호제법

• 유클리드 호제법이란 두 수의 최대 공약수를 구하는 알고리즘이다.
• 일반적으로는 두 수를 소인수 분해 후 공통된 소수들의 곱으로 표현할 수 있으나, 유클리드 호제법은 더 간단!
  • 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
  • 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD 연산을 수행한다.
  • 위 과정을 반복하다 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

https://www.acmicpc.net/problem/1934

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b, a%b) # 재귀 형태로 구현
    
t = int(input())

for i in range(t):
    a,b = map(int, input().split())
    result = a*b/gcd(a,b)
    print(int(result))

• 최소공배수는 두 수의 곱/최대 공약수로 구할 수 있다.

 

https://www.acmicpc.net/problem/1850

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b, a%b) # 재귀 형태로 구현
    
a,b = map(int, input().split())
result = gcd(a,b)

while result>0 : # result값만큼 반복하여 1 출력
    print(1, end='')
    result -=1

• 주어진 두 길이의 최대공약수를 구한 후 길이를 1로 나타내 구할 수 있다.

 

https://www.acmicpc.net/problem/1033

N = int(input()) # 재료의 개수
A = [[] for _ in range(N)] # 인접 리스트
visited = [False]*N # DFS에서 탐색 여부 저장 리스트
D = [0]*N # 각 노드값 저장 리스트
lcm = 1 # 최소 공배수

def gcd(a, b): # 최대공약수 함수 구현
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    
def DFS(v): # DFS 탐색 함수 구현
    visited[v]=True
    for i in A[v]:
        next = i[0]
        if not visited[next]: # 방문하지 않은 노드면
            D[next] = D[v]*i[2]//i[1] # 다음 노드의 값 = 현재 노드의값*비율
            DFS(next)

for i in range(N-1):
    a,b,p,q = map(int, input().split())
    A[a].append((b,p,q))
    A[b].append((a,q,p))
    lcm *= (p*q//gcd(p,q)) # 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것

D[0]=lcm # 0번 노드에 최소 공배수 저장
DFS(0)
mgcd=D[0]

for i in range(1, N):# DFS를 이용해 업데이트 된 D리스트의 값들의 최대 공약수 계산
    mgcd = gcd(mgcd, D[i])

for i in range(N): # D 리스트의 각 값을 최대 공약수로 나눠 정답 출력
    print(int(D[i]//mgcd), end=' ')

• 먼저 각 자료의 비율 자료를 그래프로 구현한다. (A 리스트에 저장)
• 데이터를 저장할 때마다 비율과 관련된 수들의 최소 공배수를 업데이트 한다.
• 임의의 시작점(D[0])에 최대 공배수 값을 저장한다.
• 임의의 시작점에서 DFS로 탐색을 수행하면서 각 노드의 값을 이전 노드의 값과의 비율 계산을 통해 계산하고 저장한다.
  • 노드 0에서 시작하는 경우, 0->4->1->2->3 순으로 탐색하게 된다.
  • 예를 들어, 노드 4번(D[next])에는 0번 노드값(D[v])*비율(i[2]//i[1]) 값이 저장된다.
• 각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력한다.

 

---

# 7-4. 확장 유클리드 호제법

• 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다.
• 해를 구하고자 하는 방정식은 ax + by = c(a,b,c,x,y는 정수)
• 이때 위 방정식은 c%gcd(a,b) = 0인 경우에만 정수해를 가진다. 
  • 5x+9y = 2일 때 이 식을 만족하는 정수 x,y를 구한다. 이때 c의 최솟값이 gcd(5,9)=1이므로 식을 5x+9y=1로 다시 놓고 진행한다.
  • a,b로 유클리드 호제법을 방복 실행하며 몫, 나머지를 저장한다. 반복은 나머지가 0이 되면 중단한다.
  • 반복문으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며 x = y', y = x'-y'*q를 계산한다. x'는 이전 x, y'는 이전 y', q는 현재 보고있는 몫을 의미한다. 처음 시작하는 x,y는 각각 1,0으로 지정하여 역계산을 진행한다.
  • 이렇게 재귀 방식으로 알아낸 최종 x,y는 ax +by = gcd(a,b)를 만족한다. c/gcd(a,b) = K로 가정하면 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있다.

 

https://www.acmicpc.net/problem/21568

잉? 제출함이 없다.

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    
def Execute(a,b):
    ret = [0]*2
    if b == 0: # 재귀함수를 중단하고 x,y를 1,0으로 설정하여 return
        ret[0] = 1
        ret[1] = 0
        return ret
    q = a//b
    v = Execute(b, a%b) # 재귀 형태로 유클리드 호제법 수행
    ret[0] = v[1] # 역순으로 올라오면서 x,y를 계산하는 로직
    ret[1] = v[0] - v[1]*q
    return ret

mgcd = gcd(a,b)

if c%mgcd != 0: # c가 최대 공약수의 배수가 아니면 -1 출력
    print(-1)
else:
    mok = int(c/mgcd)
    # 나머지(b)가 0이 될 때까지 재귀 함수를 호출하는 유클리드 호제법 함수 호출
    ret = Execute(a,b)
    # 결과값에 c/최대 공약수의 값을 곱한 후 해당 값 출력
    print(ret[0]*mok, end=' ')
    print(ret[1]*mok)

• 앞서 소개한 확장 유클리드 호제법을 그대로 구현.

 

---

# 회고

 

많은 코테의 기본이 되는 정수론을 배웠다.

이런 기본을 응용하면 더 어려워지는 듯.

확장 유클리드 호제법은 걍 뭔소린지 모르겠다...ㅎ 다시 읽어봐야지.