Coding 공부

import sys
input = sys.stdin.readline
def check(num):
    visited[num] = True
    stack = [num]

    while stack:
        node = stack.pop(0)

        for next_node in tree[node]:
            if tree[node][next_node] == 1:
                if not visited[next_node]:
                    visited[next_node] = True
                    stack.append(next_node)
                    tree[node][next_node] = 0
                    tree[next_node][node] = 0
                else:
                    return False
    return True
            


tc = 1
while True:
    N,M = map(int,input().split())
    if N+M == 0:
        break
    parent_cnt = [0]*(N+1)
    tree = [{} for _ in range(N+1)]
    for _ in range(M):
        x,y = map(int,input().split())
        tree[x][y] = 1
        tree[y][x] = 1
    cnt = 0
    visited = [False]*(N+1)
    for num in range(1,N+1):
        if not visited[num]:
            if check(num):
                cnt += 1
    if cnt == 0:
        print(f'Case {tc}: No trees.')
    elif cnt == 1:
        print(f'Case {tc}: There is one tree.')
    else:
        print(f'Case {tc}: A forest of {cnt} trees.')


    tc += 1

def find_prime_number():
    global N
    numbers = [True]*(N+1)
    numbers[0] = False
    numbers[1] = False

    for num in range(2,N+1):
        if numbers[num]:
            for num_multi in range(num*2,N+1,num):
                numbers[num_multi] = False
    prime_number = []
    for num in range(N+1):
        if numbers[num]:
            prime_number.append(num)
    return prime_number



N = int(input())


prime_numbers = find_prime_number()
DP = [0]*40001



DP[0] = 1
for prime_number in prime_numbers:
    for num in range(prime_number,N+1):
        DP[num] = (DP[num]+DP[num-prime_number])%123456789


print(DP[N])

from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline
N, D,K,C = map(int,input().split())
a = defaultdict(int)

sushi = deque()
max_value = 0
# D 초밥의 가짓수
# K 는 연속해서 먹은 초밥의 수
# C 쿠폰번호
sushi_dict = defaultdict(int)
cnt = 0
sushi_list = [int(input()) for _ in range(N)]
for left in range(N+K+1):
    sushi_input = sushi_list[left%N]
    if len(sushi)<K:
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if len(sushi) == K:
            if sushi_dict[C]>0:
                max_value = max(max_value,cnt)
            else:
                max_value = max(max_value,cnt+1)
    else:
        remove_sushi = sushi.popleft()
        sushi_dict[remove_sushi] -= 1
        if sushi_dict[remove_sushi] == 0:
            cnt -= 1
        sushi.append(sushi_input)
        if sushi_dict[sushi_input] == 0:
            cnt += 1
        sushi_dict[sushi_input] += 1
        if sushi_dict[C]>0:
            max_value = max(max_value,cnt)
        else:
            max_value = max(max_value,cnt+1)

print(max_value)

def check(x,y,size):
    for nx in range(x,x+size):
        for ny in range(y,y+size):
            if result[nx][ny] != 0:
                return False
    return True


def divide_and_fill(x,y,size):
    global numbers
    numbers += 1
    next_size = size//2
    input_position = [[x+next_size-1,y+next_size-1],[x+next_size,y+next_size-1],[x+next_size-1,y+next_size],[x+next_size,y+next_size]]
    for ind,val in enumerate([[x,y],[x+next_size,y],[x,y+next_size],[x+next_size,y+next_size]]):
        sx,sy = val
        input_x,input_y = input_position[ind]
        if check(sx,sy,next_size):
            result[input_x][input_y] = numbers

    if size == 2:
        return
    divide_and_fill(x,y,next_size)
    divide_and_fill(x+next_size,y,next_size)
    divide_and_fill(x,y+next_size,next_size)
    divide_and_fill(x+next_size,y+next_size,next_size)




k= int(input())
N = 2**k
input_x,input_y = map(int,input().split())
x = N-input_y
y = input_x-1
result = [[0 for _ in range(N)] for _ in range(N)]
result[x][y] = -1

numbers = 0
divide_and_fill(0,0,N)
for row in result:
    print(*row)

1

import sys

input = sys.stdin.readline

def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


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

make_set = [i for i in range(N+1)]
rank =  [1 for _ in range(N+1)]
for _ in range(M):
    command, A,B = map(int,input().split())

    if command:
        if find_parent(A) == find_parent(B):
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')
    else:
        union(A,B)

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
S = [0]*N
E = [0]*N
for _ in range(M):
    x, y = map(lambda x : x-1 ,list(map(int,input().split())))

    S[x] += 1
    E[y] += -1




ind = 0
result = 0
big_cnt = 0
while ind<N:
    if big_cnt:
        big_cnt += S[ind] + E[ind]
        if big_cnt == 0:
            result += 1
        ind += 1
    else:
        if S[ind] == 0:
            result += 1
        else:
            big_cnt += S[ind]
        
        ind += 1
print(result)

import sys

input = sys.stdin.readline


N = int(input())
tree = [[-1 for _ in range(2)] for _ in range(N+1)]
for i in range(1,N+1):
    left_ndoe,right_node = map(int,input().split())
    tree[i][0] = left_ndoe
    tree[i][1] = right_node



K = int(input())
cu_node = 1
while K >=0:
    left_or_right = K%2
    
    if tree[cu_node][0] != -1 and tree[cu_node][1] != -1:
        if left_or_right:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]
        K = K//2 + left_or_right
    else:
        if tree[cu_node][0] == -1 and tree[cu_node][1] == -1:
            break
        elif tree[cu_node][1] == -1:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]

print(cu_node)

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


N = int(input())
arr =list(map(int,input().split()))

arr.sort()

left_side = [0]*N
right_side = [0]*N
left_idx = 0
right_idx = 1
left_side[0] = arr[0]
right_side[-1] = arr[-right_idx]
for _ in range(N-1):
    left_gcd = gcd(left_side[left_idx],arr[left_idx+1])
    right_gcd = gcd(right_side[-right_idx],arr[-(right_idx+1)])
    left_side[(left_idx+1)] = left_gcd
    right_side[-(right_idx+1)] = right_gcd
    left_idx += 1
    right_idx += 1
result_gcd = -1
remove_data = -1
for i in range(N):
    remove_value = arr[i]
    if i == 0 or i == N-1:
        if i == 0:
            total_gcd = right_side[1]
        else:
            total_gcd = left_side[-2]
        if remove_value%total_gcd:
            if result_gcd < total_gcd:
                result_gcd = total_gcd
                remove_data = remove_value
    else:
        left_gcd = left_side[i-1]
        right_gcd = right_side[i+1]
        total_gcd = gcd(left_gcd,right_gcd)
        if remove_value%total_gcd:
            if result_gcd < total_gcd:
                result_gcd = total_gcd
                remove_data = remove_value

if result_gcd == -1:
    print(result_gcd)
else:
    print(result_gcd,remove_data)