주차장 안내등의 공통 눈금

문제

한 주차장은 긴 진입로를 따라 안내등을 설치하려 한다. 진입로에는 기준점이 하나 정해져 있고, 안내등을 놓아야 하는 위치는 기준점에서 떨어진 정수 거리로 기록되어 있다. 여러 안내 목적이 같은 위치를 지정할 수 있으므로 기록된 거리 중에는 같은 값이 여러 번 나타날 수도 있다. 같은 위치가 여러 번 기록되어 있어도 설치 조건은 한 번 기록된 경우와 같다. 시공팀은 일정한 간격으로 눈금이 새겨진 측정 띠를 사용한다. 눈금 간격 d는 2 이상 L 이하인 정수 중에서 선택한다. 또한 띠를 놓을 때 기준점과 첫 눈금 사이의 어긋남 r을 정수로 정하며, 0 ≤ r < d를 만족해야 한다. 간격과 어긋남을 정하면 눈금이 있는 위치는 r, r+d, r+2d, r+3d, …가 된다. 이 눈금 중 일부에 안내등을 설치하며, 안내등을 설치하지 않는 눈금이 있어도 괜찮다. 선택한 간격 d를 사용할 수 있으려면, 기록된 모든 안내등 위치가 눈금 위에 놓이도록 하는 어긋남 r이 하나 이상 존재해야 한다. 하나의 간격에 대해 가능한 어긋남을 여러 번 세지는 않는다. 즉, 구하려는 것은 조건을 만족하는 서로 다른 간격 d의 개수다. 기록된 위치가 모두 같더라도 이 규칙을 그대로 적용한다. 측정 띠의 길이는 충분하므로 마지막 눈금이나 띠의 끝은 고려하지 않는다. 예를 들어 간격이 5이고 어긋남이 2라면 위치 2, 7, 12에는 모두 안내등을 설치할 수 있지만 위치 8에는 설치할 수 없다. 위치를 옮기거나 기준점을 바꾸는 것은 허용되지 않으며, 간격마다 어긋남만 새로 선택할 수 있다. 위치 기록과 간격의 상한 L이 주어질 때 사용할 수 있는 간격의 개수를 구하는 프로그램을 작성한다. 가능한 간격이 없으면 0을 출력한다.

입력

첫째 줄에 두 정수 N과 L이 공백으로 구분되어 주어진다.
둘째 줄에 안내등 위치를 나타내는 N개의 정수 X_1, X_2, ..., X_N이 주어진다. 위치는 정렬되어 있지 않을 수 있고, 같은 값이 여러 번 주어질 수 있다.
1 ≤ N ≤ 100,000, 2 ≤ L ≤ 1,000,000,000이며, 모든 i에 대해 0 ≤ X_i ≤ 1,000,000,000이다.

출력

조건을 만족하는 서로 다른 정수 간격 d의 개수를 정수 하나로 출력한다. 가능한 간격이 없으면 0을 출력한다.

4 10
2 14 26 38

4

3 5
7 7 7

4

3 100
0 6 11

0

출처: Devin.KR 자체 제작