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 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector a(n);
    for (int i=0;i> a[i];
    long long ans = 0;
    // map: gcd_value -> count of subarrays ending at current index
    map prev;
    for (int i=0;i 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 << "
";
    return 0;
}