GCD of Contiguous Subsequence

2 secs 1024 MB
take44444's icon take44444

問題文

長さNNの数列AAが与えられます.数列AAの空でない連続部分列で,全要素の最大公約数がMMとなるものの個数を求めてください.

ただし,部分列の要素が同じでも、取り出す位置が異なっていれば別の部分列として数えます.

また,数列の要素が11つの場合はその要素の値を最大公約数とします.つまり,任意の自然数xxについて,gcd(x)=x\gcd(x) = xです.

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ai,M1018(1iN)1 \leq A_i, M \leq 10^{18} \quad (1 \leq i \leq N)
  • 入力はすべて整数

入力

N MN\ M
A1ANA_1 \dots A_N

出力

数列AAの空でない連続部分列で,全要素の最大公約数がMMとなるものの個数を求めてください.

サンプル

入力例1
5 10
12 48 24 30 20
出力例1
1

数列AAの空でない連続部分列で,全要素の最大公約数が1010となるものは以下の11つのみです.

  • [30,20][30, 20]
入力例2
5 6
12 48 24 30 20
出力例2
3

数列AAの空でない連続部分列で,全要素の最大公約数が66となるものは以下の33つです.

  • [12,48,24,30][12, 48, 24, 30]
  • [48,24,30][48, 24, 30]
  • [24,30][24, 30]

Submit


Go (1.21)