解题思路

• 末尾连续零来源于因子 2 与 5 的配对，某段乘积末尾零的个数等于 min(2 的总次数, 5 的总次数)。

• 将每个元素 a[i] 拆成 (cnt2[i], cnt5[i])，其中 cntp[i] 是 a[i] 中质因子 p 的个数（只需分解 2 和 5，反复整除即可）。

• 问题转化为：统计区间 [l, r] 使得 sum2(l, r) ≥ k 且 sum5(l, r) ≥ k。 这是一个双指针/滑动窗口问题（所有计数均为非负）。

• 具体做法

  1. 预处理得到 cnt2[i], cnt5[i]。

题目内容

给定一个长度为 $n$ 的正整数数组 {$a_1,a_2,...,a_n$} 和一个正整数 $k$，我们称子数组 $[l,r]$ 的乘积末尾包含至少 $k$ 个连续零，为可整除子数组。

请统计满足上述条件的子数组个数。

输入描述

第一行输入两个整数 $n(1≦n≦2×10^5)$ 与 $k(1≦k≦10^9)$ ，分别表示数组长度与所需的末尾零个数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦a_i< 10^9)$，表示数组元素。

输出描述

输出一个整数，表示乘积末尾至少包含 $k$ 个连续零的子数组总数。

样例1

输入

5 1
10 5 2 25 50

输出

12

说明

在此样例中，所有满足条件的子数组共有 $12$ 个。其中 $[1,1],[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4,[3,5],[4,5],[5,5]$ 均满足条件。

样例2

输入

3 2
100 10 5

输出

3

说明

在此样例中，可选子数组为 $[1,1],[1,2],[1,3]$，它们的乘积末尾均包含至少 $2$ 个零。