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

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 . 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 . She calls the Carol-dividing number of the number of divisions of required to reduce it to . As some examples, the Carol-dividing number of is , the Carol-dividing number of is , and the Carol-dividing number of is .

Given an array of numbers and an integer , calculate the number of contiguous subarrays in which the Carol-dividing number of the greatest common factor is equal to . In other words, find the number of ranges, and , such that the greatest number which divides has Carol-dividing number equal to .

Input Specification

The first line will contain , the size of the array and the designated number of common factors. The next lines will contain the integers .

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.