시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 3 1 33.333%

문제

Masz dane n zbiorów, z których i-ty zawiera liczby ai·di, (ai+1)·di, (ai+2)·di, …, bi·di Nazwijmy sumę tych wszystkich zbiorów S. Policz, ile jest w zbiorze  liczb, które są względnie pierwsze z daną liczbą m.

입력

W pierwszym wierszu znajdują się liczby n i m (1 ≤ n ≤ 16, 1 ≤ m ≤ 109). Każdy z kolejnych  n wierszy zawiera liczby całkowite ai, bi, di pooddzielane pojedynczymi odstępami (1 ≤ ai,bi,di ≤ 1018, ai ≤ bi, bi·di ≤ 1018).

 

출력

W jedynej linii wyjścia powinna znaleźć się jedna liczba całkowita, odpowiedź na pytanie z zadania.

예제 입력 1

3 6
1 5 2
3 7 5
3 5 7

예제 출력 1

2

출처

Camp > POI Training Camp > ONTAK 2008 63번

  • 잘못된 데이터를 찾은 사람: cubelover