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 in C++
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for (int i=0;i<n;i++) cin >> a[i];
long long ans = 0;
// map: gcd_value -> count of subarrays ending at current index
map<int, int> prev;
for (int i=0;i<n;i++){
map<int,int> curr;
curr[a[i]]++;
for(auto &p: prev) {
int g = gcd(p.first, a[i]);
curr[g] += p.second;
}
ans += curr[1];
prev = curr;
}
cout << ans << "\n";
return 0;
}