chminoo   11달 전

화나넹

암튼 질문은 다음과 같습니다

이문제가 결론적으로 요구하는건

1 <= x <= n 인 n^2의 약수 x의 개수를 구하는 문제인데

전수탐색으로는 역시 시간초과가 납니다

n이 10억까지 가니까...

처음에 생각했던건

n^2를 소인수 분해 해서 약수의 개수를 구하고 (약수의갯수-1)/2+1 하는 거였는데

생각해보니 소인수 분해가 더 오래걸리겠더라고요 특히 10억^2 범위안에 소수걸리면 끝이니까

그래서 저런식으로 바꿔서 생각해봤는데 저기서 진전이 없습니다

도와주세요~~

ho94949   11달 전

n을 소인수 분해 한 결과로 n^2의 소인수 분해를 구하는 방법은 없을까요?

chminoo   11달 전

아이고 감사합니다

마침 그렇게 새로 생각해서 풀어서 맞췄는데 답변주셨네요 ㅋㅋㅋ

n을 소인수분해해서 갯수를 구할때 2를 곱해주는식으로 맞췄습니다. 답변감사합니다!!

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