블로그 이사 중입니다 >> gumgood.github.io

3474 교수가 된 현우 본문

Problem Solving/문제 풀이

3474 교수가 된 현우

gumgood 2018. 11. 8. 15:40

C++11


n!의 오른쪽 끝에 있는 0의 개수를 구하는 문제


n!의 소인수들로 10을 몇 개나 만들 수 있는지 묻는 것이다.


1~n 사이의 수들의 소인수 중에 2와 5가 몇 개인지 찾으면 그 중 작은 값이 10의 개수임을 알 수 있다.



n의 범위는 10^9이므로 O(n)에는 돌릴 수 없다.


'1~n의 소인수 중에 2와 5의 개수'를 쉽게 세는 방법이 있다.


n까지의 수 중 2의 배수는 n/2

+

n까지의 수 중 4의 배수는 n/4

+

n까지의 수 중 8의 배수는 n/8

+

...


와 같이 count 하면


소인수에 2^k를 포함하는 수는 k번 세어지므로 O(log2(n))에 2의 개수를 구할 수 있다.


5의 개수 역시 같은 방법으로 O(log5(n))에 구할 수 있다.



O(logn)

'Problem Solving > 문제 풀이' 카테고리의 다른 글

4246 To and Fro  (0) 2018.11.08
4659 비밀번호 발음하기  (0) 2018.11.08
3474 교수가 된 현우  (0) 2018.11.08
4690 완전 세제곱  (0) 2018.11.08
4641 Doubles  (0) 2018.11.08
6376 e 계산  (0) 2018.11.08
0 Comments
댓글쓰기 폼