B-평활수

시간 제한1초메모리 제한128 MB

요약

구간 [n, n+m]에 들어 있는 B-매끄러운 수, 즉 B 이하의 소인수만 가진 수의 개수를 센다. n은 최대 20억, m은 최대 1억, B는 최대 100만이다.

난이도: 어려움10점 중 8점
유형: 정수론, 세그먼트 트리, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

양의 정수 $B$ 가 주어진다. 양의 정수 $x$ 의 모든 소인수가 $B$ 이하일 때, $x$ 를 $B$ -평활수( $B$ -smooth number)라고 한다. 이는 $x$ 를 각각 $B$ 이하인 양의 정수들의 곱으로 나타낼 수 있다는 것과 같은 뜻이다. (특히 $1$ 은 모든 $B$ 에 대해 $B$ -평활수이다.)

세 양의 정수 $n$ , $m$ , $B$ 가 주어질 때, 닫힌구간 $[n,\ n+m]$ 안에 있는 $B$ -평활수의 개수를 구하라.

입력

한 줄에 세 정수 $n$ , $m$ , $B$ 가 공백 하나로 구분되어 주어진다. ( $1 \le n \le 2\,000\,000\,000$ , $1 \le m \le 100\,000\,000$ , $1 \le B \le 1\,000\,000$ )

출력

구간 $[n,\ n+m]$ 안에 있는 $B$ -평활수의 개수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
30 10 5
```
예상 출력
```
4
```
예제 2
입력
```
1 100 2
```
예상 출력
```
7
```