<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 greatest common divisor 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>greatest common divisor of an array</strong> is the largest integer that evenly divides all the array elements.</p>

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

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

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

<pre>
<strong>Input:</strong> nums = [4], k = 7
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no subarrays of nums where 7 is the greatest common divisor 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;= 10<sup>9</sup></code></li>
</ul>

# O(n log n) time to build, O(combineFn) time to query, so & is O(1) since AND-ing two numbers is constant

class SparseTable:
    def __init__(self, nums, combineFn):
        BITS = math.ceil(math.log2(len(nums))) + 1

        # Initialize the sparse table for all windows of length 1
        sparse = [[None] * len(nums) for _ in range(BITS)] # sparse[log][left] is the answer to the fn operator for the subarray [left:left+2**power]
        for left in range(len(nums)):
            sparse[0][left] = nums[left]

        for log in range(1, BITS):
            for left in range(len(nums)):
                right = left + 2**log - 1
                if right >= len(nums):
                    break
                leftHalfAnswer = sparse[log - 1][left]
                rightHalfAnswer = sparse[log - 1][int(left + (2**(log - 1)))]
                combinedAnswer = combineFn(leftHalfAnswer, rightHalfAnswer)
                sparse[log][left] = combinedAnswer

        self.sparse = sparse
        self.combineFn = combineFn

    def query(self, l, r):
        width = r - l + 1
        power = math.floor(math.log2(width))
        windowWidth = 2**power
        leftAnswer = self.sparse[power][l]
        rightSideStart = r - windowWidth + 1
        rightAnswer = self.sparse[power][rightSideStart]
        combinedAnswer = self.combineFn(leftAnswer, rightAnswer)
        return combinedAnswer

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        def combineFn(a, b):
            return math.gcd(a, b)
        
        sparse = SparseTable(nums, combineFn)

        # as we move right, the gcd is mono decreasing
        ans = 0
        for l in range(len(nums)):
            print(f'iter on left edge l={l}')
            # find the leftmost r where [l:r] is k
            left = l
            right = len(nums) - 1
            res = None
            while left <= right:
                print(f'iter left={left} right={right}')
                m = (right + left) // 2
                print(f'testing m: {m}')
                gcd = sparse.query(l, m)
                print(f'gcd from l: {l} to m: {m} is: {gcd}')
                
                # if the gcd is too big, we must move right
                if gcd > k:
                    print(f'gcd too big, must move right')
                    left = m + 1
                # if the gcd is equal, update res, but try moving more left
                elif gcd == k:
                    print(f'gcd is k, update res and move left')
                    res = m
                    right = m - 1
                # if gcd is too small, we must move left
                else:
                    right = m - 1
            print(f'the leftmost r where [l:r] is k: {res}')
            
            leftmost = res

            if leftmost == None:
                continue

            print('FINDING RIGHTMOST')
            # find the rightmost r where [l:r] is k
            left = res
            right = len(nums) - 1
            res = None
            while left <= right:
                print(f'iter left={left} right={right}')
                m = (right + left) // 2
                print(f'testing m: {m}')
                gcd = sparse.query(l, m)
                print(f'gcd from l: {l} to m: {m} is {gcd}')

                # if the gcd is too big, we must move right
                if gcd > k:
                    print(f'gcd too big, must move right')
                    left = m + 1
                # if the gcd is equal, update res, but try moving more right
                elif gcd == k:
                    print(f'gcd is k, update res and move left')
                    res = m
                    left = m + 1
                # if gcd is too small, we must move left
                else:
                    right = m - 1
            print(f'the rightmost r where [l:r] is k: {res}')

            if res != None:
                width = res - leftmost + 1
                ans += width
        return ans

        # res = 0
        # for l in range(len(nums)):
        #     currGcd = nums[l]
        #     for r in range(l, len(nums)):
        #         currGcd = math.gcd(currGcd, nums[r])
        #         if currGcd < k:
        #             break
        #         res += currGcd == k
        # return res

204