GCD of Subarrays
HardPractice library · +30 XPmathnumber theorygcd
Given an array A of N positive integers, find the number of subarrays whose greatest common divisor (GCD) is exactly K. A subarray is a contiguous part of the array. The GCD of a single element subarray is the element itself.
Input
The first line contains two integers N and K. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer, the count of subarrays whose GCD is exactly K.
Constraints
1 <= N <= 200000, 1 <= K <= 10^9, 1 <= A_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
6 2 2 4 6 8 10 12
Output
16
Subarrays with GCD 2 are: [2], [2,4], [2,4,6], [2,4,6,8], [2,4,6,8,10], [2,4,6,8,10,12], [4,6], [6,8], [8,10], [10,12].
Example 2
Input
5 3 3 9 6 15 12
Output
11
Subarrays with GCD 3 are: [3], [3,9], [3,9,6], [9,6], [6], [6,15], [6,15,12], [15], [15,12], [12].
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
6 2 2 4 6 8 10 12
Example 2 input
5 3 3 9 6 15 12