Number of Subarrays With GCD Equal to K

Count the number of contiguous subarrays whose greatest common divisor equals k. Exploit that the running GCD of a subarray only decreases, so for each start index you can extend while maintaining/updating the GCD and stop early when it drops below or is no longer a multiple of k (O(n^2) viable for n ≤ 1000).