글 읽기 - 시간초과문제ㅠㅠ

wkddbwls4982 5년 전 0

무한 루프를 쓰지 않고 이중 for문을 이용해서 문제를 풀었는데 시간초과라고 뜹니다...

해결할 방법이 없을까용ㅠㅠㅠㅠㅠ 도와주세요

n=int(input())

gcdCount=0
for k in range(1,n+1):
    for i in range(1,k+1):
        if n%i==0 and k%i==0:
            gcd=i
    if gcd==1:
        gcdCount+=1            

print(gcdCount)

chogahui05 5년 전 2

이중 for문을 도니까 시간 초과가 뜨지요.. O(n)도 시간초과 뜨는데

O(n^2)는 말할 것도 없겠죠.

O(root(n))만에 해결할 수 있는 방법을 찾아봅시다.

jyuno426 5년 전 0

1. n 이하의 자연수 중, n과 서로소인 수의 갯수를 구하는 오일러 피 함수
2. 소인수분해를 sqrt(n) (루트 n)의 시간복잡도로 하는 방법

위 두가지를 공부하시면 문제를 푸실 수 있습니다!

https://ko.wikipedia.org/wiki/...

https://ratsgo.github.io/data%...

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

문제

문제

출처

ICPC

시간초과문제ㅠㅠ

wkddbwls4982 5년 전 0

chogahui05 5년 전 2

jyuno426 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말