kjk9704   1년 전

큰 수 소인수분해(4149번) 문제를 먼저 해결하여 최적화된 소인수분해를 하고 그 다음 오일러 피 함수를 적용했더니 이 문제를 한방에 맞췄습니다.

이 문제는 밀러-라빈 소수 판별법과 폴라드 로 알고리즘으로 빠르게 소인수들을 구하는 것이 핵심입니다.


추가로 테스트 케이스 공유합니다.

factories   1년 전

P.S. Python 기준으로 이 문제에서 "/" + "int"는 사용하지 마세요! "//" 쓰는게 안전합니다. (제가 저거 썼다가 4번정도 틀렸어요)

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