13926번 - gcd(n, k) = 1
큰 수 소인수분해(4149번) 문제를 먼저 해결하여 최적화된 소인수분해를 하고 그 다음 오일러 피 함수를 적용했더니 이 문제를 한방에 맞췄습니다.
이 문제는 밀러-라빈 소수 판별법과 폴라드 로 알고리즘으로 빠르게 소인수들을 구하는 것이 핵심입니다.
추가로 테스트 케이스 공유합니다.
P.S. Python 기준으로 이 문제에서 "/" + "int"는 사용하지 마세요! "//" 쓰는게 안전합니다. (제가 저거 썼다가 4번정도 틀렸어요)
댓글을 작성하려면 로그인해야 합니다.
kjk9704 1년 전 3
큰 수 소인수분해(4149번) 문제를 먼저 해결하여 최적화된 소인수분해를 하고 그 다음 오일러 피 함수를 적용했더니 이 문제를 한방에 맞췄습니다.
이 문제는 밀러-라빈 소수 판별법과 폴라드 로 알고리즘으로 빠르게 소인수들을 구하는 것이 핵심입니다.
추가로 테스트 케이스 공유합니다.