
[백준 Java] 1407번 2로 몇 번 나누어질까
·
Algorithm/PS - 백준
💡문제[Gold IV] 2로 몇 번 나누어질까 - 1407문제 링크성능 요약메모리: 11552 KB, 시간: 76 ms🌟풀이범위가 무려 1≤A≤B≤1015 로 엄청나다.그래서 A ~ B 까지 순회하면서 더할 수는 없다.1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다.💡 1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ?1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20-1-2-1-3-1-2-1-4-1-21부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다.이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다.위를 참고하여| 1 | 2 | 3 | ..