3109 : 두 수의 곱의 약수 개수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 14
•통과: 4
•만든사람: suakii
문제 설명
두 자연수 $A$와 $B$가 주어졌을 때, 두 수의 곱 $A \times B$의 약수의 개수를 구하는 프로그램을 작성하세요.
단, $A \times B$는 최대 $10^{12}$(1조)에 달할 수 있으므로, $1$부터 $A \times B$까지 모두 나누어보는 단순 반복문 방식($O(A \times B)$)은 시간 초과(TLE)가 발생합니다.
소인수분해의 성질을 활용하여 효율적으로 약수의 개수를 구해야 합니다.
힌트: 소인수분해 결과가 $p_1^{e_1} \times p_2^{e_2} \times \dots$ 일 때, 약수의 총 개수는 $(e_1 + 1)(e_2 + 1)\dots$ 입니다.
[제약 조건]
• $1 \le A, B \le 1\,000\,000$
• $A, B$는 자연수
• 제한 시간: 1.0초
입력 설명
첫째 줄에 두 자연수 $A$와 $B$가 공백으로 구분되어 주어집니다.
출력 설명
$A \times B$의 약수의 개수를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
4×6=24=2³×3¹ → (3+1)(1+1)=8... 아, 4=2², 6=2×3이므로 24=2³×3¹ → (3+1)(1+1)=8