题目大意：

给一段序列a[i],求有m个询问，每个询问有一个x，求有多少个区间gcd恰好为x

数据范围：

对于100%的数据，n,m≤1e5,a[i],x≤2e9

思路：

对于一段序列，gcd下降的速度极快，所以整个序列存在的gcd总数不会特别多。

至多log2e9 ??不会证明

考虑存在以每一个节点为结尾存在的gcd种类及数量，每次不断向后更新，用map存所有出现过的gcd值和出现次数

 

!!!!除了线段树维护gcd外，另一种gcd的维护方法!!记录

以下代码：

#include
      
       #define il inline#define LL long long#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e5+5;int n,m;vector
       
        
          > g[N];map
         
           ma;il int read(){
    int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}il int gcd(int x,int y){
    if(x>y)swap(x,y);if(x==0)return y;return gcd(y%x,x);}int main(){    n=read();    for(int i=1;i<=n;i++){        int last=-1;int x=read();int k=-1;        for(int j=0;j