rt，[ARC023D] GCD区間和CF475D

我的代码自认为是 $n\log^2 n$ 的，但是都 T 了，求助，哪里写假了？

#include <bits/stdc++.h>
using namespace std;

#define LL long long

const int N=1e5+5;

int n,q;
int a[N],st[N][20]; 

map<int,LL> mp;

int gcd(int a,int b){if(!b) return a;return gcd(b,a%b);};

int qry(int x,int y){
   int S=__lg(y-x+1);
   return gcd(st[x][S],st[y-(1<<S)+1][S]);
}

int main(){
   ios::sync_with_stdio(0),cin.tie(0);
   cin>>n>>q;
   for(int i=1;i<=n;i++){
   	cin>>a[i];
   	st[i][0]=a[i];
   }
   for(int j=1;j<=19;j++){
   	for(int i=1;i+(1<<j)-1<=n;i++){
   		st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
   	}
   }
   for(int x=1;x<=n;x++){
   	int i=x,pre=i;
   	while(i<=n){
   		int gc=qry(x,i);
   		for(int j=19;j>=0;j--){
   			if(st[i][j]==gc){
   				i=i+(1<<j)-1;
   			}
   		}
   		mp[gc]+=i-pre+1;
   		pre=i+1;
   		i++;
   	}
   }
   while(q--){
   	int x;
   	cin>>x;
   	cout<<mp[x]<<"\n";
   }
   return 0;
}