★Number Theory Upper-Intermediate I - 8 Solved★

★ 1850 최대공약수 ★

import math

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

ans = ''.join(['1']*math.gcd(A,B))

print(ans)

 

👑 1의 개수 A와 B의 최대공약수만큼 1이 나열되어 있는 수가 최대공약수. 최대공약수 성질 / 유클리드 호제법을 사용해 이를 증명해보자

 

※ 1이 a개 있는 수와 1이 b개 있는 수의 최대공약수는 1이 gcd(a,b)개 있는 수 (a≥b)※

 

- 증명 - 

→ 1이 a개 있는 수를 $S_a$, 1이 b개 있는 수를 $S_b$라고 하면

$$S_a = \underbrace{111 ... 111}$$

(1이 a개)

$$S_b = \underbrace{111 ... 111}$$

(1이 b개)

 

→ 아래와 같이 10의 지수승으로 나열할 수 있다.

$$S_a = 10^{a-1} + 10^{a-2} ... + 10^0$$

$$S_b = 10^{b-1} + 10^{b-2} ... + 10^0$$

 

→ 10^(n-1)로 간단히 나타내자면

$$S_a = \frac{10^a-1}{9}$$

$$S_b = \frac{10^b-1}{9}$$

 

→ 9로 동시에 나누었으므로, 최대공약수의 성질에 의해 $S_a, S_b$의 최대공약수는 $10^a-1, 10^b-1$의 최대공약수에 9를 나눈 결과임을 알 수 있다.

 

→ 즉, gcd($10^a-1$,$10^b-1$)에 관해 식으로 풀어쓰면 (q >= 1, 0 <= r < b) (a=bq+r)

$$gcd(10^a-1,10^b-1)$$

$$=gcd(10^{qb+r}-10^r+10^r-1,10^b-1)$$

$$=gcd(10^r(10^{qb}-1)+10^r-1,10^b-1)$$

 

→ $gcd(A,B) = gcd(A-NB,B)$에 의해

$$=gcd(10^b-1,10^r-1)$$

$$(N = \frac{10^r(10^{ab}-1)}{10^b-1})$$

 

→ 따라서, $gcd(10^a-1, 10^b-1) = gcd(10^b-1, 10^r-1)$

 

→ 연쇄적으로 r이 0이 될 때, 즉 유클리드 호제법에 의해 $gcd(10^a-1, 10^b-1) = 10^{gcd(a,b)}-1$

 

→ 따라서, $S_a, S_b$의 최대공약수는 $\frac{10^{gcd(a,b)}-1}{9}$

 

→ 등비수열 합 공식에 의해 

$10^{gcd(a,b)}-1 = (10-1)(10^{gcd(a,b)-1}+10^{gcd(a,b)-2}+...+1)$

 

→ $S_a, S_b$의 최대공약수는 최종적으로

$$10^{gcd(a,b)-1}+10^{gcd(a,b)-2}+...+1$$

 

→ 이는 1이 총 $gcd(a,b)$개 있는 수이다. 증명 끝!

---

★ 17087 숨바꼭질 6 ★

import sys
input=sys.stdin.readline

def gcd(a,b):
    A,B=max(a,b),min(a,b)

    while B>=1:
        A,B=B,A%B
    return A
N,S=map(int,input().split())
l=[]
for x in input().split():
    l.append(abs(S-int(x)))
ans=l[0]
for x in l[1:]:
    ans=gcd(ans,x)
print(ans)

👑 두 개 이상의 수들의 최대공약수 구하기

: D 보폭만큼 동생을 만날 수 있으므로 모든 동생을 찾기 위해서는 D가 공약수. 근데 D의 최댓값을 구해야 하므로 이는 최대공약수 구함

 

👑 두 개 이상의 최대공약수 구하는 방법:

: 앞에서 차례대로 두 개의 최대공약수를 구하고, 그 결과를 그 다음 수와의 최대공약수 구하고, 또 그 결과를 그 다음 수와의 최대공약수를 구하면서 연쇄적으로 최대공약수를 2개 쌍끼리 구해 나가면 됨!

---

★ 22302 Factorial Factors ★

 

import sys
input=sys.stdin.readline

sieve = [True]*(100_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=[x for x in range(len(sieve)) if sieve[x]]

for _ in range(int(input())):
    N=int(input())
    ans=[]
    for prime in primes:
        if prime > N:
            break
        square=1
        while 1:
            share=int(N/(prime**square))
            if share == 0:
                break
            else:
                ans.extend([prime]*share)
            square+=1
    print(len(set(ans)),len(ans))

 

👑 입력받은 N의 N! 소인수 분해를 진행하는 문제. 제일 작은 소수부터 소수의 제곱수를 N에 나누면 된다. 예를 들어 5!의 소인수분해는 곧 1 x 2 x 3 x 4 x 5 이므로 소수 2부터 시작해서 int(N/2) + int(N/2**2) + int(N/2**3)의 개수를 누적. [prime]*share를 list에 update. 그 다음 소수 3도 마찬가지.

---

★ 9020 골드바흐의 추측 ★

💁🏻‍♂️ 골드바흐 수 = 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.

💁🏻‍♂️ 골드바흐 파티션 = 짝수를 두 소수의 합으로 나타내는 표현

 

💁🏻‍♂️ 골드바흐 파티션을 출력하는 유형! (두 소수의 차이가 작은 쌍)

import sys
input=sys.stdin.readline

def first_goldbach(n):
    arr = [True] * n 
    arr[0]=False
    end = int(n**(1/2))
    for i in range(2,end+1):
        if arr[i-1] == True:
            for k in range(i-1,n,i):
                arr[k] = False
            arr[i-1] = True
    
    for j in range(n//2,0,-1):
        if arr[j] == True == arr[(n-2-j)]:
                ans = j+1
                break

    return ans

for _ in range(int(input())):
    N=int(input())
    a=first_goldbach(N)
    print(min(a,N-a),max(a,N-a),sep=' ')

 

💁🏻‍♂️ 여러 쌍이 존재한다면, 두 소수의 차이가 가장 적은 쌍부터 출력하므로, 정수론에 의해 두 수 중 한 개의 수는 전체 크기의 절반보다 작거나 같은 값이기 때문에,range(n//2,0,-1) 범위를 두어 차례대로 계산

 

💁🏻‍♂️ 소수 판정법은 에라토스테네스의 체 사용. 두 수의 array값이 모두 True라면 골드바흐 파티션 조건 충족! 바로 출력

(추가 - 성능을 더 높일려면 테스트 케이스에 주어진 n 중 최댓값만 골라 단 1개의 에라토스테네스의 체를 만들어 판정하는 게 더 빠름)

---

★ 17103 골드바흐 파티션 ★

 

import sys
input=sys.stdin.readline

#sieve of eratosthenes (size 1_000_000)
sieve=[True]*1_000_001
sieve[0],sieve[1]=False,False

for i in range(2,1_000_001):
    if sieve[i] == True:
        for j in range(i,1_000_001,i):
            sieve[j] = False
        sieve[i] = True

for _ in range(int(input())):
    N = int(input())
    ans = 0
    for i in range(2,N//2+1):
        if sieve[i] == True and sieve[N-i] == True:
            ans += 1
    print(ans)

 

💁🏻‍♂️먼저 최댓값 백만까지의 에라토스테네스의 체를 만들고 난 뒤(시간 효율을 위해 에라토스테네스의 체는 한 번만 생성), 골드바흐의 추측을 만족하는 두 소수를 구해야 하므로, N의 절반까지만 돌며 sieve 체의 i와 N-i 두 쌍이 각자 True로 나온다면 합으로 카운트

---

★ 25632 소수 부르기 게임 ★

import sys
input=sys.stdin.readline

sieve = [True]*(1001)
sieve[0],sieve[1] = False, False

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

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

yt=[prime for prime in primes if A <= prime <= B]
yj=[prime for prime in primes if C <= prime <= D]

if len(yt)!=len(yj):
    if len(yt)>len(yj):
        print('yt')
    else:
        print('yj')
    sys.exit()

same = set(yt).intersection(set(yj))
if len(same)%2 == 1:
    print('yt')
else:
    print('yj')
    
#####

same = set(yt).intersection(set(yj))
turn = 1
while True:
    if turn == 1:
        if len(yt) == 0:
            print('yj')
            break
        if len(same) > 0:
            discard_elem = list(same)[0]
            same.discard(discard_elem)
            yt.remove(discard_elem)
            yj.remove(discard_elem)
        else:
            yt.pop()
        turn = 0
    else: #turn = 0
        if len(yj) == 0:
            print('yt')
            break
        if len(same) > 0:
            discard_elem = list(same)[0]
            same.discard(discard_elem)
            yt.remove(discard_elem)
            yj.remove(discard_elem)
        else:
            yj.pop()
        turn = 1

 

💁🏻‍♂️ 직접 시뮬레이션으로 돌리거나 / 교집합 소수의 개수에 따른 게임 이론 판정으로 풀 수 있다.

 

① 일단 각 범위 내의 두명 각각의 소수 list 구하기

② 더 많은 소수를 가진 사람 '승'

③ 서로 가진 소수가 같을 경우, 교집합 소수의 개수가 짝수라면 먼저 진행한 용태 승리 / 홀수라면 이후에 진행한 유진 승리

→ 그리디에 의해 게임 이론으로 각 플레이어가 매 상황 상황 이기기 위해 최선을 다한다 했으므로, 무조건 교집합 소수를 선택해서 제거. 따라서 교집합 소수가 짝수라면 교집합 소수를 다 없애고 난 다음 용태 차례이므로 용태 승리 / 홀수라면 교집합 소수를 다 없애고 난 다음 유진 차례이므로 유진 승리

---

★ 1747 소수&팰린드롬 ★

def get_sieve(l):
    sieve = [True]*(l+1)
    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
    return sieve
sieve = get_sieve(1003001)
N=int(input())

for prime in range(len(sieve)):
    if str(prime) == str(prime)[::-1] and prime >= N and sieve[prime]:
        print(prime)
        break

 

💁🏻‍♂️ 백만초과의 소수 중 팰린드롬 최솟값은 1003001임을 알고 1003001까지의 에라토스테네스의 체 만든 다음 BF로 돌려 팰린드롬이면 출력하고 끝

---

★ 6588 골드바흐의 추측 ★

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

import sys
input=sys.stdin.readline

while 1:
    n=int(input())
    if n == 0: break
    found=False
    for i in range(n-3,2,-2): #3~(n-3)
        if sieve[i] and sieve[n-i]:
            found=True
            print(f'{n} = {n-i} + {i}')
            break
    if not found:
        print("Goldbach's conjecture is wrong.")

 

💁🏻‍♂️ 에라토스테네스의 체를 쓰되 시간초과에 유의해야 하는 문제. 일단 √n까지만(n은 sieve 전체 크기) 돌리고, 내부 for문을 2*x부터 돌린다.

 

💁🏻‍♂️ for i in range(n-3,2,-2) 즉 가능 소수는 3 ~ (n-3)까지만 가능하므로 n-3부터 3까지 -2의 step으로 돌린다. 소수가 존재하는지 in 연산자 사용 없이, 에라토스테네스의 체 index를 활용해 if sieve[i] and sieve[n-i]인 조건을 사용해 문제 소수 판별.

---