Given an integer array nums and an integer k, return the number of subarrays of nums where the least common multiple of all elements in the subarray is equal to k.

Note: A subarray is defined as a contiguous non empty sequence of elements within an array. The least common multiple of an array of numbers is the smallest positive integer that is evenly divisible by all elements in that array.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $1 \leq$ nums[i], k $\leq 1000$

Input: nums = [7, 14, 2, 28]-List[int], k = 14-int
Output: 4-int
Explanation: The subarrays with LCM equal to 14 are [7, 14], [14], [14, 2], and [7, 14, 2], giving a total of 4.

Input: nums = [5, 10, 15]-List[int], k = 12-int
Output: 0-int
Explanation: No subarray has an LCM equal to 12, so the count is 0.

Input: nums = [1, 1, 1, 1]-List[int], k = 1-int
Output: 10-int
Explanation: Every non-empty subarray consists only of 1s and has an LCM of 1. There are \(4 + 3 + 2 + 1 = 10\) such subarrays.

Input: nums = [2, 6, 4, 3, 12, 5]-List[int], k = 12-int
Output: 10-int
Explanation: The subarrays within the prefix ending at 12 whose LCM is 12 total 10. Any subarray containing 5 cannot have an LCM of 12.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.