★Number Theory Intermediate I - 17 Solved★

★ 9613 GCD 합 ★

 

import sys
input=sys.stdin.readline
from itertools import combinations

def gcd(a,b): #a<=b
    while a>0:
        a,b=b%a,a
    return b

for _ in range(int(input())):
    ans = 0
    pairs = list(combinations(list(map(int, input().split()))[1:], 2))
    for pair in pairs:
        ans += gcd(pair[0], pair[1])
    
    print(ans)

 

🦙 최대공약수 GCD를 구하는 알고리즘은 크게 아래와 같이 3가지로 나눌 수 있다.

① math module 내장함수 사용

② 유클리드 호제법 사용 (별도 gcd 함수 따로 만들기 / 재귀)

③ 정의 - 공약수 중 최댓값

 

※ 정수론의 성질 중 하나 [유클리드 호제법]을 사용해 GCD를 구하는 방법이 정의를 이용한 방법보다 성능이 빠르다

 

🦙 itertools의 combinations(또는 두 번 for loop 돌려도 된다)로 가능한 모든 pair 구한 뒤, 유클리드 호제법 적용하면 끝!

---

★ 10610 30 ★

 

import sys
input=sys.stdin.readline

N = list(map(int, input().rstrip()))

if sum(N)%3 == 0 and 0 in N:
    N.sort(reverse=True)
    print(int(''.join(map(str,N)))) 

else:
    print('-1')

 

🦙 30의 배수 판정법 → 10의 배수 (0이 존재하는 지 판별) + 3의 배수 (3으로 나눈 나머지가 0)

---

★ 6872 RSA Numbers ★

 

def if_RSA(n):
    cnt=0
    end=int(n**(1/2))
    for i in range(1,end+1):
        if n%i==0:
            if i!=(n//i): cnt+=2
            else: cnt+=1
    if cnt==4:return True
    else:return False

a=int(input())
b=int(input())
ans=0
for n in range(a,b+1):
    if if_RSA(n):ans+=1
print(f'The number of RSA numbers between {a} and {b} is {ans}')

 

🦙 약수 판정은 전체 수까지 돌릴 필요 없고, 전체 수의 root 범위까지만 돌리면 된다(시간복잡도 O(N) → O(root(N)). 이 때, 제곱수일 경우 카운팅되므로, 약수의 개수는 1만 추가해주고, 나머지 수는 2개씩 cnt 변수 증가시켜주면 끝!

---

★ 14650 걷다보니 신천역 삼 (Small) ★

 

N=int(input())
print(0 if N==1 else 2*3**(N-2))

 

🦙 정수론) 3의 배수는 모든 수의 합이 3의 배수이다

 

🦙 dp를 적용하면, N자리 3의 배수 개수를 a(n)이라고 한다면,

a(n) = a(n-1)*3 (n ≥ 3; a(1) = 0, a(2) = 2)

① a(n-1)에서 이미 만들어진 3의 배수들 중, 3을 맨 앞과 맨 뒤에 붙인다면 정수론 성질에 의해 3의 배수가 된다.

ex) 121212가 있을 때, 맨 앞에 3을 붙인 3121212 또는 맨 뒤에 3을 붙인 1212123은 모두 3의 배수

 

② a(n-1)에서 이미 만들어진 3의 배수들 중, 0을 맨 뒤에 붙인다면 정수론 성질에 의해 3의 배수가 된다.

ex) 121212가 있을 때, 맨 뒤에 0을 붙인 1212120도 3의 배수

 

∴ 즉, 이미 앞에서 만들어진 수 121212에서 총 3가지의 경우로 3의 배수를 만들 수 있으므로 x3을 해준다!

∴ 3만 계속 곱해지므로 등비수열로 점화식이 아닌, 등비수열 공식으로 나타낼 수 있다.

a(n) = 2 * 3^(n-1) (n ≥ 3)

---

★ 14651 걷다보니 신천역 삼 (Large) ★

N=int(input())
print(0 if N==1 else ((2*3**(N-2))%(1_000_000_009)))

---

★ 1735 분수 합 ★

 

a1,b1=map(int,input().split())
a2,b2=map(int,input().split())

A,B=a1*b2+a2*b1,b1*b2

def gcd(a,b): #a<=b
    while a>0:
        a,b=b%a,a
    return b
k=gcd(A,B)
print(A//k,B//k)

 

🦙 두 분수의 합을 구하고, 분자와 분모 각각 최대공약수로 나눈 결과인 분자와 분모로 이루어진 분수가 최종 답. 최대공약수를 구할 때, 유클리드 호제법을 사용: 유클리드 호제법 - 큰 수를 작은 수로 나눈 나머지와 작은 수를 계속 반복 - 최종적으로 작은 수가 0이 될 때까지 반복

---

★ 13241 최소공배수 ★

 

A,B=map(int,input().split())
a,b=max(A,B),min(A,B)
while b!=0:
    if a%b==0:
        a=b
        break
    a,b=b,a%b
print(A*B//a)

 

🦙 A*B = G*L이라는 공식, 즉 두 수의 곱은 최대공약수와 최소공배수의 곱이라는 것만 정확히 알면, 유클리드 호제법으로 최대공약수를 구하고 바로 최소공배수를 구할 수 있다! 유클리드 호제법을 코드로 나타내면 큰 수에서 작은 수로 나누고 작은 수가 0이 될 때까지 반복, 이 때 도중에 b가 a에 나누어지면 b 자체가 최대공약수가 되므로 바로 break 탈출해 최대한 시간 단축

---

★ 13909 창문 닫기 ★

 

🦙 창문을 열고 닫는 횟수가 홀수 번이어야 최종적으로 열린다. 열고 닫는 횟수는 약수의 개수를 뜻하므로, 약수의 개수가 홀수 개라는 건, 곧 제곱수임을 뜻한다. n이하의 제곱수의 개수를 출력하면 끝!

---

★ 1929 소수 구하기 ★

 

M,N=map(int,input().split())

#에라토스테네스의 체
l=[True]*N #먼저 True
end=int(N**0.5) #제곱근까지만 iteration

#l=[1,2,3,~,N]이고 [T,T,~,T] array
#l's index [0,1,2,~N-1]

for i in range(2,end+1): #i자체가 소수판정대상 number - i's iteration
    if l[i-1]==True: #index는 i-1
        for k in range(i-1,N,i):l[k] = False #i의 배수가 되는 모든 number False
        l[i-1]=True #나 자신은 True로

ans=[i+1 for i in range(1,N) if l[i] == True] #l's [2,3,~,N]에서 True 고르기

print(*[i for i in ans if i>=M],sep='\n') #이 중 M이상인것만 고르기

 

👳🏻‍♀️ 소수 판별법을 다시 요약하면,

① 2부터 (자기자신-1)까지 모두 자기자신에서 나누었을 때 나머지가 0이 아니다 → 소수의 정의를 이용 O(N)

② 약수의 개수가 2이다 → O(N)

③ 약수의 개수가 2이다 - 검사범위 N의 제곱근까지 → O(root(N))

④ 약수의 개수가 2이다 - 검사범위 N/2까지 → O(N)

⑤ 에라토스테네스의 체 → O(Nlog(logN)))

⑥ 2와 3 제외 소수는 6으로 나눈 나머지가 1 또는 5

 

👳🏻‍♀️ 위 문제를 맞을려면 ⑤ 에라토스테네스의 체를 사용해야 한다.

 

① 총 N개의 True값이 적혀 있는 array 생성

② True라고 적힌 원소부터(1 제외) N까지 해당 원소의 배수들 모두 False로 바꿈

(단, 자기 자신은 다시 True로 바꿈)

※ 전체 N까지 돌 필요 없고 root(N)을 내림한 자연수까지 돌면 됨

③ 1 제외 True라고 적힌 모든 원소들이 N이하의 소수들

 

👳🏻‍♀️ 위 코드 풀이

① 총 N개의 True가 담긴 list + 탐색 끝 end는 N의 제곱근까지

② i는 탐색 수로, 2부터 end까지 for문 설정

③ index는 i-1로, l[i-1] 값이 True라면, 해당 위치부터 index 기준 N-1까지 (즉, 수로는 i부터 N까지) i씩 점프하며, 점프되는 곳은 i의 배수이므로 False 설정

④ 여기서 시작점 자체는 다시 True로 설정

⑤ 완료! True인 것만 빼서 별도 list 설정하고 M이상인 것만 골라서 출력!

---

★ 2960 에라토스테네스의 체 ★

 

N,K=map(int,input().split())
l=[True]*N

s=0
y=0
for i in range(2,N+1):
    if l[i-1] == True:
        for k in range(i-1,N,i):
            if l[k]==True:
                l[k]=False
                s+=1
            if s==K:
                y=1
                print(k+1)
                break
    if y==1: break

 

👳🏻‍♀️ False가 되는, 원하는 순서에 맞는 지워지는 수를 찾아 출력하면 끝! + greedy하게, 원하는 K번째 수를 찾았으면 내부 for문 break + flag 변수로 바깥 for문 break 설정

---

★ 9842 Prime ★

 

n=int(input())
N=110000
#Sieve of Eratosthenes (size of N)
arr=[True]*N
arr[0]=False
for i in range(2,N+1):
    if arr[i-1]==True:
        for j in range(i-1,N,i):arr[j]=False
        arr[i-1]=True
primes_arr=[i+1 for i in range(1,N) if arr[i]==True]
print(primes_arr[n-1])

 

👳🏻‍♀️ 최대 10000개의 소수를 담을 수 있는 에라토스테네스의 체 범위는 자연수 104729까지라고 한다! ㅎㅎ

---

★ 6219 소수의 자격 ★

 

A,B,D=map(int,input().split())

arr=[True]*B
arr[0]=False
end=int(B**(1/2))
cnt=0

for i in range(2,end+1):
    if arr[i-1]==True:
        for j in range(i-1,B,i):arr[j]=False
        arr[i-1]=True

for n in range(A-1,B):
    if arr[n] == True and str(D) in str(n+1): cnt+=1
print(cnt)

 

👳🏻‍♀️ 크기 B에 해당하는 에라토스테네스의 체를 만든 뒤, 체의 index+1이 곧 판정대상인 숫자가 되고, 체의 내용이 T/F이므로 이를 적절히 range()문으로 판별하면 끝!

---

★ 4948 베르트랑 공준 ★

 

import sys
input=sys.stdin.readline

def Sieve_of_Eratosthenes(N):
    arr=[True]*(N+1)
    arr[0],arr[1]=False,False
    end=int(N**(1/2))

    for i in range(2,end+1):
        if arr[i] == True:
            for j in range(i,N+1,i):
                arr[j] = False
            arr[i] = True
    return arr


while True:
    N = int(input())
    if N == 0: break
    sieve = Sieve_of_Eratosthenes(2*N)
    print(sum(sieve)-sum(sieve[:N+1]))

 

👳🏻‍♀️ 2n까지의 에라토스테네스의 체 만들고, n까지의 범위 True 개수 빼면 끝!

---

★ 4134 다음 소수 ★

 

import sys
input=sys.stdin.readline
N=int(input())

def isPrime(n):
    end=int(n**(1/2))
    for i in range(2,end+1):
        if n%i==0:
            return False
    return True

for _ in range(N):
    x = int(input())
    if x <= 1: print(2)
    else:
        while True:
            if isPrime(x):
                print(x)
                break
            x+=1

 

👳🏻‍♀️ 소수 판정 알고리즘 ③ ($\sqrt{N}$) 사용

---

★ 24039 2021은 무엇이 특별할까? ★

 

import sys

sieve=[True]*(10_001)
sieve[0],sieve[1]=False,False
for x in range(2,int(len(sieve)**(1/2))+1):
    if sieve[x]:
        for y in range(x,len(sieve),x):
            sieve[y]=False
        sieve[x]=True
primes=[]
for x in range(len(sieve)):
    if sieve[x]:
        primes.append(x)

N=int(input())
x=N
while 1:
    x+=1
    for y in range(2,int(x**(1/2))+1):
        if x%y==0 and sieve[y]:
            k=primes.index(y)
            if x==(y*primes[k+1]):
                print(x)
                sys.exit()

 

👳🏻‍♀️ 에라토스테네스의 체 활용해서 연속한 소수의 곱 판별 한번에 쉽게!

---

★ 1476 날짜 계산 ★

 

E,S,M=map(int,input().split())

if E == 15: E = 0
if S == 28: S = 0
if M == 19: M = 0

share=-1
while True:
    share+=1
    N=share*15+E
    if N%28==S and N%19==M and N > 0:
        print(N)
        break

 

👳🏻‍♀️ 15, 28, 19로 나눈 나머지가 E, S, M인 N을 출력(단 E, S, M이 15, 28, 19일 때는 0으로 설정)

---

★ 2485 가로수 ★

import sys,math
input=sys.stdin.readline

N=int(input())
ts=sorted([int(input()) for _ in range(N)])
Is=[ts[i]-ts[i-1] for i in range(1,N)]
cur=Is[0]
for interval in Is[1:]: cur = math.gcd(cur,interval)
print(((ts[-1]-ts[0])//cur+1)-N)

👳🏻‍♀️ 가로수들 사이의 간격의 최대공약수만큼 간격으로 가로수를 심어야 가로수 간격이 모두 동일. 여러 공약수 중 최대공약수의 간격이 곧 심을 수 있는 가로수를 최솟값으로 심을 수 있게 된다.

---