Problem Description

Xiao Lan has an array $A = (a_1,a_2,\cdots,a_n)$ of length $n$. A subarray is defined as an array formed by selecting one or more consecutive elements from the original array. The greatest common divisor (GCD) of an array refers to the GCD of all elements in the array. If, after changing at most one element in the array, the GCD of the array becomes $g$, then $g$ is called the approximate GCD of this array. An array may have multiple possible approximate GCD values.

Specifically, to determine whether $g$ is an approximate GCD of a subarray:

1. If the GCD of this subarray is exactly $g$, then $g$ is its approximate GCD.
2. If, after modifying one element in this subarray (it can be changed to any value), the GCD of the subarray becomes $g$, then $g$ is the approximate GCD of this subarray.

Xiao Lan wants to know how many subarrays of $A$ with length at least $2$ have an approximate GCD equal to $g$.

Input Format

The first line contains two integers $n,g$, separated by a space, representing the length of array $A$ and the value of $g$.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, with a space between adjacent integers.

Output Format

Output one line containing one integer, representing how many subarrays of array $A$ with length at least $2$ have an approximate GCD equal to $g$.

5 3
1 3 6 4 10

5

Hint

Sample Explanation

There are $5$ subarrays that satisfy the condition:

$[1,3]$: After changing $1$ to $3$, the GCD of this subarray becomes $3$, so it satisfies the condition.

$[1,3,6]$: After changing $1$ to $3$, the GCD of this subarray becomes $3$, so it satisfies the condition.

$[3,6]$: The GCD of this subarray is $3$, so it satisfies the condition.

$[3,6,4]$: After changing $4$ to $3$, the GCD of this subarray becomes $3$, so it satisfies the condition.

$[6,4]$: After changing $4$ to $3$, the GCD of this subarray becomes $3$, so it satisfies the condition.

Constraints

For $20\%$ of the testdata, $2\le n\le100$.

For $40\%$ of the testdata, $2\le n\le1000$.

For all testdata, $2\le n\le10^5$, $1\le g,a_i \le10^9$.

Lanqiao Cup 2022 National Contest, Group C, Problem F.

Translated by ChatGPT 5