집합

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

요약

d_i의 배수로 이루어진 n개의 등차수열 집합의 합집합에서 m과 서로소인 원소의 개수를 구한다.

난이도: 어려움10점 중 9점
유형: 수학, 정수론, 조합론, 구간
정답자: 아직 제출이 없습니다

문제

$n$ 개의 집합이 주어집니다. $i$ 번째 집합은 다음 수들을 담고 있습니다.

$a_i \cdot d_i,\ (a_i+1)\cdot d_i,\ (a_i+2)\cdot d_i,\ \ldots,\ b_i \cdot d_i$

이 모든 집합의 합집합을 $S$ 라고 합시다. 집합 $S$ 의 원소 중에서 주어진 수 $m$ 과 서로소인 (즉, $m$ 과의 최대공약수가 $1$ 인) 수가 몇 개인지 세어 주세요.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어집니다 ( $1 \le n \le 16$ , $1 \le m \le 10^9$ ).

이어지는 $n$ 개의 줄에는 각각 세 정수 $a_i$ , $b_i$ , $d_i$ 가 공백 하나로 구분되어 주어집니다 ( $1 \le a_i, b_i, d_i \le 10^{18}$ , $a_i \le b_i$ , $b_i \cdot d_i \le 10^{18}$ ).

출력

집합 $S$ 의 원소 중 $m$ 과 서로소인 원소의 개수를 한 줄에 정수 하나로 출력합니다.

예제6

예제 1
입력
```
3 6
1 5 2
3 7 5
3 5 7
```
예상 출력
```
2
```
예제 2
입력
```
1 7
1 10 1
```
예상 출력
```
9
```
예제 3
입력
```
2 1
1 3 1
2 5 1
```
예상 출력
```
5
```
예제 4
입력
```
2 1
1 5 2
1 5 2
```
예상 출력
```
5
```
예제 5
입력
```
1 12
1 12 1
```
예상 출력
```
4
```
예제 6
입력
```
3 10
1 6 1
4 9 1
1 3 3
```
예상 출력
```
4
```