题解

气死我了，给个 hack：

200000
114514 114514 ...
1
114514 

200000
1 2 3 4 5 6 ...
1
1

这两组数据会将“此用户已被标记为棕名”的代码卡到 $O(n^2)$。

---

题意解析：给定一个长度为 $n$ 的数组 $A$。$q$ 次询问，每次询问给定一个数 $v$，求有多少 $l\le r$ 满足 $\gcd\{A_l,...,A_r\}=v$。

首先因为一个区间的 $\gcd$ 一定是它子区间 $\gcd$ 的因数，所以势能分析一下，对于任意一个 $l$，$[l,n]$ 一定可以分成不超过 $\log_2 V$ 段，每段内区间 $\gcd$ 值相同。

所以我们只需要求出所有段就可以得出所有答案了。

显然可以用 ST 表 $O(n\log n\log V)$ 实现。

namespace cjdst{
    template <typename T>
	class Sparse_Table{
		std::vector <std::vector <T>> st;
		int n;

		public:

		Sparse_Table(int n, std::vector <T> a){
			this -> n = n;
			st.resize(a.size() + 5, std::vector <T>(std::__lg(n) + 5));
			for(int i = 1; i <= n; i++){
				st[i][0] = a[i];
			}
			for(int i = 1; i <= std::__lg(n); i++){
				for(int j = 1; j <= n; j++){
					if(j + (1 << i) - 1 > n) break;
					st[j][i] = std::__gcd(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
				}
			}
		}

		T next(int idx, int val){
			for(int i = std::__lg(n); i >= 0; i--){
				if(st[idx][i] % val == 0 && (idx + (1 << i) <= n + 1)) idx += (1 << i);
			}
			return idx;
		}
	};
    
    void solve(){
		int n, m;
		std::cin >> n;
		std::vector <int> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		std::map <int, ll> ans;
		Sparse_Table <int> st(n, a);
		for(int i = 1; i <= n; i++){
			int cur = i, val = a[i];
			while(cur <= n){
				int nxt = st.next(cur, val);
				ans[val] += nxt - cur;
				cur = nxt, val = std::__gcd(val, a[nxt]);
			}
		}
		std::cin >> m;
		while(m--){
			int val;
			std::cin >> val;
			std::cout << ans[val] << '\n';
		}
	}
}

有人可能会说：诶你这计算 $\gcd$ 不算时间复杂度吗？其实势能分析一下，对于一个数 $V$ 进行 $n$ 次 $\gcd$ 运算，最多只会算 $n+\log_2 V$ 次。所以次数可以忽略不计。

Bonus：单点改，区间求。显然可以做到 $O(q\sqrt{n\log V\log\log V})$。