글 읽기 - 시간 복잡도를 줄일 방법?

sksms1375 2년 전 0

n까지 소수를 에라토스테네스의 체로 구하고 n!과 k!, (n-k)!가 2부터 n까지의 소수로 몇개가 나누어지는지 계산한 후 n!은 분자고, k!, (n-k)!은 분모니 여기서 빼주는 방식을 이용했습니다 이후 모듈러 연산을 수행했습니다

처음에는 거듭제곱이 시간복잡도를 잡아먹을거 같아서 분할 정복 거듭제곱을 이용했는데 TLE가 계속 나와서 제가 생각할 수 있는 것 중에는 개선 방안이 안보입니다

좋은 방법 없을까요?

from math import sqrt

n, k, m = map(int, input().split())
prime = [1, 1] + [0] * (n-1)
for i in range(2, int(sqrt(n))+1):
    if prime[i] == 0:
        j = 2
        while i*j <= n:
            prime[i*j] = 1
            j += 1
prime_number = []
n_factory = {}
for i in range(2, n+1):
    if prime[i] == 0:
        n_factory[i] = 0
        prime_number.append(i)
for i in prime_number:
    j = i
    while j <= n:
        n_factory[i] += (n//j) - (k//j) - ((n-k)//j)
        j *= i
answer = 1
for i, j in n_factory.items():
    if j != 0:
        v, sq = 1, i
        for s in reversed(bin(j)[2:]):
            if s == '1':
                v = (v*sq)%m
            sq = sq**2%m
        answer *= v%m
    if answer == 0:
        print(0)
        exit()
print(answer%m)

kdh9949 2년 전 1

30번째 줄에서 answer *= v%m을 하는데, 여기서 answer에 mod를 취해 주지 않아서 값이 계속 커지고, 그럼에 따라 계산에 걸리는 시간이 늘어납니다. 따라서 여기가 계산을 느리게 하는 병목이 됩니다.

지금 코드에서 여기만 고치면 맞습니다.

sksms1375 2년 전 0

아 정작 저쪽에는 나누지를 않았네요 좋은 지적 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 복잡도를 줄일 방법?

sksms1375 2년 전 0

kdh9949 2년 전 1

sksms1375 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말