A. Orac and Factors

문제

예시

[input]
3
5 1
8 2
3 4

[output]
10
12
12

답1 – 이곳을 클릭하면 정답이 보입니다
def fn(n):
    for i in range(2, int((n**0.5))+1):
        if n%i == 0:
            return i
    return n

def answer(n, k):
    n = fn(n) + n
    return n + (2*(k-1))
    
testCount = int(input())
for _ in range(testCount):
    n, k = map(int, input().split())
    print(answer(n, k))

우선 나눠지는 수중 가장 작은 수를 구하기 위해서 2 ~ n까지가 아니라 루트n까지만 돌면 된다는점, 그리고 fn(n) + n은 무적권 짝수가 되기 때문에 2만 (k-1)번 더해주면 된다는점이 포인트이다.

답2 – 이곳을 클릭하면 정답이 보입니다

설명

B. Orac and Models

문제

예시

[input]
4
4
5 3 4 6
7
1 4 2 3 6 4 9
5
5 4 3 2 1
1
9

[output]
2
3
1
1

답1 – 여기를 클릭하면 정답이 보입니다
def answer(arr):
    n = len(arr)
    history = [0]*(n+1)
    stack = [[1, 1, 0]]
    while(len(stack) != 0):
        stack[-1][1] += 1
        a = stack[-1]
        b = a[0]*(a[1])
        if b <= n:
            if arr[a[0]-1] < arr[b-1]:
                if history[b] is 0:
                    stack.append([b, 1, 0])
                else:
                    stack[-1][2] = max(stack[-1][2], history[b]+1)
        else:
            p = stack.pop()
            if len(stack) > 0:
                stack[-1][2] = max(stack[-1][2], p[2]+1)
                history[stack[-1][0]] = max(history[stack[-1][0]], stack[-1][2]) 
            if len(stack) == 0 and p[0] < n:
                stack = [[p[0]+1, 1, 0]]
    return max(history)+1
    
testCount = int(input())
for _ in range(testCount):
    n = int(input())
    arr = list(map(int, input().split()))
    print(answer(arr))

어후… 너무 힘들었다. 이게 B번 문제 맞나? 내가 너무 어렵게 풀은건가??? 암튼….진짜 4시간은 푼것같다. 힘들다.

답2 – 여기를 클릭하면 정답이 보입니다

설명

C. Orac and LCM

문제

예시

[input]
2
1 1

[output]
1

[input]
4
10 24 40 80

[output]
40

[input]
10
540 648 810 648 720 540 594 864 972 648

[output]
54

답1 – 여기를 클릭하면 정답이 보입니다
def gcd(a, b):
    b, a = sorted([a, b])
    while(b != 0):
        a, b = (b, a%b)
    return a

def lcm(a, b):
    c = gcd(a, b)
    return (a//c)*(b//c)*c

def gcds(arr):
    for i in range(len(arr)-1):
        arr[i+1] = gcd(arr[i], arr[i+1])
    return arr[-1]
        
def answer(arr):
    n = len(arr)
    t = []
    for i in range(n):
        for j in range(i+1, n):
            t.append(lcm(arr[i], arr[j]))
        t = [gcds(t)]
    return t[-1]
    
n = int(input())
arr = list(map(int, input().split()))
print(answer(arr))

이게 말은 맞는데 시간이 터진다. 100,000의 제곱만큼 연산이 발생하기 때문에 오래걸린다. 어떻게 줄이지?

답2 – 여기를 클릭하면 정답이 보입니다

설명