Dwight is always bragging about how amazing he is at solving complicated problems with much ease. Jim got tired of this and gave him an interesting problem to solve.

Jim gave Dwight a sequence of integers a1, a2, …, an and q queries x1, x2, …, xq on it. For each query xi Dwight has to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and GCD(al, al + 1, …, ar) = xi. Dwight is feeling out of his depth here and asked you to be his Secret Assistant to the Regional Manager. Your first task is to help him solve the problem. Are you up to it?

## The GCD Dilemma

Given a sequence of integers a1, …, an and q queries x1, …, xq on it. For each query xi, you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(al, al + 1, …, ar) = xi. The GCD Dillema.

#include <iostream>

#include <map>

#include <vector>

using namespace std;

int gcd(int a, int b) {

if (a % b == 0) return b;

return gcd(b, a % b);

}

int main() {

ios_base::sync_with_stdio(false);

int n; cin >> n;

vector<int> v(n);

for(int i=0;i<n;i++)

cin>>v[i];

map<int, long long> results;

map<int, int> divisors;

map<int, int> nextDivisors;

for (int i = 0 ; i < n ; i++)

{

nextDivisors.clear();

for (auto &p : divisors)

{

nextDivisors[gcd(p.first, v[i])] += p.second;

}

nextDivisors[v[i]]++;

swap(nextDivisors, divisors);

for (auto &p : divisors)

results[p.first] += p.second;

}

int q; cin >> q;

while (q --> 0) {

int x; cin >> x;

cout << results[x] << endl;

}

}

Minimum In Subarray Segment Tree

Palindrome Partitioning GFG Solution

Show Comments