13926번 - gcd(n, k) = 1
이 문제를 풀기 위해서 인터넷 여기저기 정말 열심히 돌아다녔는데 O(N^1/2)보다 빠른 알고리즘을 찾지 못했습니다. (11689번 문제를 풀고 큐브러버님의 코드를 봐서 약간의 최적화하는 방법을 배웠습니다.)
여기서 두 가지로 갈리는데
만약 다른 알고리즘이 있다면 2번은 무시해주세요.
아무튼 이 문제의 접근 방법을 알고 싶습니다.
풀지 않아서 확실한 답변은 못 드립니다만, Pollard rho algorithm일걸요?
저도 폴라드 로 썼어요
@bessapple14 문제를 착각하신 것 아닌가요? 이 문제는 11689번보다 제한이 더 큰 다른 문제입니다.
역시 다른 알고리즘이었군요 ㅠㅠ
새롭게 공부할 게 생겼네요 감사합니당
맞았습니다 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
cheetose 6년 전
이 문제를 풀기 위해서 인터넷 여기저기 정말 열심히 돌아다녔는데 O(N^1/2)보다 빠른 알고리즘을 찾지 못했습니다. (11689번 문제를 풀고 큐브러버님의 코드를 봐서 약간의 최적화하는 방법을 배웠습니다.)
여기서 두 가지로 갈리는데
만약 다른 알고리즘이 있다면 2번은 무시해주세요.아무튼 이 문제의 접근 방법을 알고 싶습니다.