4053 : 공배수 개수
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 7
•통과: 3
•만든사람: suakii
문제 설명
$1$부터 $N$까지의 자연수 중에서 $A$의 배수이면서 동시에 $B$의 배수인 수, 즉 $A$와 $B$의 공배수의 개수를 구하는 프로그램을 작성하시오.
예를 들어 $N=30$, $A=4$, $B=6$이면 공배수는 $12, 24$이므로 개수는 2이다.
[제약 조건]
• $1 \le N \le 1\,000\,000$
• $1 \le A \le N$
• $1 \le B \le N$
• $N, A, B$는 자연수
예를 들어 $N=30$, $A=4$, $B=6$이면 공배수는 $12, 24$이므로 개수는 2이다.
[제약 조건]
• $1 \le N \le 1\,000\,000$
• $1 \le A \le N$
• $1 \le B \le N$
• $N, A, B$는 자연수
입력 설명
첫째 줄에 세 정수 $N, A, B$가 공백으로 구분되어 주어집니다.
출력 설명
$1$부터 $N$까지 $A$와 $B$의 공배수 개수를 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
30 4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
도움
$A$와 $B$의 공배수는 $\text{lcm}(A, B)$의 배수이다.
$\text{lcm}(A, B) = \frac{A \times B}{\gcd(A, B)}$
따라서 $N$ 이하의 공배수 개수 = $\lfloor N / \text{lcm}(A, B) \rfloor$
$\text{lcm}(A, B) = \frac{A \times B}{\gcd(A, B)}$
따라서 $N$ 이하의 공배수 개수 = $\lfloor N / \text{lcm}(A, B) \rfloor$