hihihi   10년 전


무슨 마법을 부리면 이 문제를 1초 안에 해결할 수 있나요?ㄷㄷ

저는 1에서 2000000까지의 정수에 대해 각각 그 수를 약수로 가지는 수의 개수를 센 다음, 그 수*개수가 최대가 되는 것을 답으로 했습니다.
근데 저 개수를 세기 위해서 N개의 수 각각의 약수를 구하는 데 root(number)만큼 걸려서 1.7초정도 걸리네요..

이 문제를 1초 내에 해결하신 분들은 대체 무슨 마법을 부리신 건가요 ㅜㅜ...

august14   10년 전

직접 소인수분해를 하셔서 약수를 구하시면 됩니다.

hihihi   10년 전

각 N개마다 소인수분해하면 O(N sqrt(M)) 아닌가욤? 

august14   10년 전

미리 소수를 직접 구해놓으면 sqrt(2000000) 이하의 소수가 300개가 안되서 빠르게 되더라구요

august14   10년 전

그리고 2000000 이하의 수 중에 약수 갯수가 가장 많은게 약수 개수가 300개가 안되서 역시 빠르게 됩니다.

hihihi   10년 전

헐 그렇군요 ........고맙습니다 !!!

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