<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>subarrays</strong> of </em><code>nums</code><em> where the least common multiple of the subarray&#39;s elements is </em><code>k</code>.</p>

<p>A <strong>subarray</strong> is a contiguous non-empty sequence of elements within an array.</p>

<p>The <strong>least common multiple of an array</strong> is the smallest positive integer that is divisible by all the array elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,6,2,7,1], k = 6
<strong>Output:</strong> 4
<strong>Explanation:</strong> The subarrays of nums where 6 is the least common multiple of all the subarray&#39;s elements are:
- [<u><strong>3</strong></u>,<u><strong>6</strong></u>,2,7,1]
- [<u><strong>3</strong></u>,<u><strong>6</strong></u>,<u><strong>2</strong></u>,7,1]
- [3,<u><strong>6</strong></u>,2,7,1]
- [3,<u><strong>6</strong></u>,<u><strong>2</strong></u>,7,1]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no subarrays of nums where 2 is the least common multiple of all the subarray&#39;s elements.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 1000</code></li>
</ul>

from functools import cache
from math import gcd


class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        """
        два поинтера, на начало и конец подмассива
        вопрос как быстро понимать, что нок = к
        нок <= к, если все числа являются делителями к
        """
        ans = 0
        for s in range(len(nums)):
            lcm = nums[s]
            for e in range(s + 1, len(nums) + 1):
                lcm = lcm * nums[e - 1] // gcd(lcm, nums[e - 1])
                # print(lcm)
                if lcm == k:
                    ans += 1
        return ans

        # import copy
        # self.d = {1: set([1]),
        #      2: set([1, 2])} # number: set of its dividers
        # self.get_dividers(k)
        # ans = 0
        # for s in range(len(nums)):
        #     if k % nums[s] != 0:
        #         continue
        #     if nums[s] not in self.d:
        #         self.get_dividers(nums[s])
        #     cur_dividers = copy.copy(self.d[nums[s]])
            
        #     for e in range(s + 1, len(nums) + 1):
        #         if k % nums[e - 1] != 0:
        #             break
        #         if nums[e - 1] not in self.d:
        #             self.get_dividers(nums[e - 1])
        #         cur_dividers |= self.d[nums[e - 1]]
        #         if self.d[k] == cur_dividers:
        #             ans += 1
        # return ans
    
    def get_dividers(self, n):
        self.d[n] = set()
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                self.d[n].add(i)
                self.d[n].add(n // i)
    
    @cache
    def gcd(self, a, b):
        if a < b:
            a, b = b, a
        if a % b == 0:
            return b
        while b != 1 and b != 0:
            a, b = b, a % b
        return a
1067