map+pair Bayan 2015 Contest Warm Up D题

Given a sequence of integers a₁,?...,?a_n andq queries x₁,?...,?x_q on it. For each queryx_i you have to count the number of pairs(l,?r) such that 1?≤?l?≤?r?≤?n and gcd(a_l,?a_l?+?1,?...,?a_r)?=?x_i.

is a greatest common divisor ofv₁,?v₂,?...,?v_n, that is equal to a largest positive integer that divides allv_i.

The first line of the input contains integer n, (1?≤?n?≤?10⁵), denoting the length of the sequence. The next line containsn space separated integers a₁,?...,?a_n, (1?≤?a_i?≤?10⁹).

The third line of the input contains integer q, (1?≤?q?≤?3?×?10⁵), denoting the number of queries. Then followsq lines, each contain an integer x_i, (1?≤?x_i?≤?10⁹).

For each query print the result in a separate line.

3
2 6 3
5
1
2
3
4
6

1
2
2
0
1

7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000

14
0
2
2
2
0
2
2
1
1

题意给你一个序列和q个询问,输出有多少个区间[l,r]满足区间gcd为询问的值。

思路：处理出每个区间的gcd(要注意合并区间)，如果有询问则直接加上去。

#include 
  
   
using namespace std;
std::map
   
     id; vector
    
      >gcdList; const int MAXN=100000+5; int query[MAXN*3],A[MAXN]; long long ans[MAXN*3]; int _gcd(int a,int b){return b?_gcd(b,a%b):a;} int ID(int x){ if(!id[x])id[x]=id.size(); return id[x]; } int main(int argc, char const *argv[]) { int n; ios_base::sync_with_stdio(false); gcdList.clear();id.clear(); cin>>n; for(int i=1;i<=n;i++)cin>>A[i]; int q;cin>>q; for(int i=1;i<=q;i++){ cin>>query[i]; query[i]=ID(query[i]); } for(int i=1;i<=n;i++){ for(int j=0;j