Problem 35: Subarray GCD 1
Problem Statement: Given an array of n positive integers, count the number of subarrays whose greatest common divisor (GCD) is 1.
Input
The first line contains the integer n. The second line contains n space-separated integers.
Output
Print the count of subarrays with GCD equal to 1.
Examples
Input:
4
2 4 3 6
Output:
4
Solution Explanation
Method 1: Use a dynamic programming approach where for each ending index, maintain a map of current GCD values and their counts. Method 2: Use a naive approach by iterating over all subarrays and computing GCD, which is too slow for large n, so DP is preferred.
Solution in C++
#include
#include
#include