Valentine's Day '18 S5 - Carol's Calculating Continuity

View as PDF

Submit solution

Points: 20
Time limit: 2.75s
Memory limit: 512M

Author:
Problem type

Carol has recently started thinking about primes, and marveling at the way in which numbers can be expressed through their prime factorization. Carol especially enjoys taking a number, and dividing it by some prime, and repeating this process until the number becomes 1. No matter what primes Carol selects along the process, she discovers that it takes exactly the same number of divisions to reduce a starting number down to 1. She calls the Carol-dividing number of X the number of divisions of X required to reduce it to 1. As some examples, the Carol-dividing number of 16 is 4, the Carol-dividing number of 12 is 3, and the Carol-dividing number of 1 is 0.

Given an array of N numbers and an integer K, calculate the number of contiguous subarrays in which the Carol-dividing number of the greatest common factor is equal to K. In other words, find the number of ranges, L and R, such that the greatest number which divides a[L], a[L+1], \dots, a[R-1], a[R] has Carol-dividing number equal to K.

Constraints

1 \le N \le 1\,000\,000

0 \le K \le \min(20, N)

1 \le a_i \le 100\,000

Input Specification

The first line will contain N, the size of the array and K, the designated number of common factors.

The next N lines will contain the integers a_i.

Output Specification

Output a single integer, as specified in the statement.

Sample Input

16 1
25
7
10
32
25
29
29
29
27
25
27
11
18
27
9
13

Sample Output

10

Explanation

The valid contiguous (0-indexed) subarrays are 1-1, 2-3, 5-5, 5-6, 5-7, 6-6, 6-7, 7-7, 11-11, 15-15.


Comments

There are no comments at the moment.