社区讨论

求问

AAIerqwq
CF475DCGCDSSQ参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mlyv7egd
此快照首次捕获于
2026/02/23 15:38
2 周前
此快照最后确认于
2026/02/25 14:42
2 周前
查看原帖
这个解法应该是 O(nlog⁡V)O(n\log V) 的，但跑起来和 O(nlog⁡2V)O(n\log^2 V) 一样，是哪里假了吗？还是单纯常数大？
解法
考虑分治。
首先依旧势能分析，发现任意一个区间 [l,r][l,r] 的前缀和后缀 gcd⁡\gcd 一定能分成 min⁡{r−l+1,⌊log⁡2V⌋}\min\{r-l+1,\lfloor\log_2 V\rfloor\} 段，每段相同。
所以合并两个区间时，我们可以枚举这两个区间的每一段计算。每左右两段会对它们区间的 gcd⁡\gcd 贡献两段长度之积。
先说结论，如果能 O(1)O(1) 求出 gcd⁡\gcd，则这个解法是 O(nlog⁡V)O(n\log V) 的。
证明：我们把这个递归树分一下层，会发现最下面 log⁡2log⁡2V\log_2\log_2 V 层合并都是 O((r−l+1)2)O((r-l+1)^2) 的，所以下面那 log⁡2log⁡2V\log_2 \log_2 V 层总的时间复杂度都是 O(nlog⁡V)O(n\log V)。再看上面的，上面的每个节点大小都在 log⁡2V\log_2 V 以上，所以所有节点数不超过 2nlog⁡2V\frac{2n}{\log_2 V}，每次合并是 O(log⁡2V)O(\log^2 V)，所以时间复杂度也是 O(nlog⁡V)O(n\log V)。
现在的问题就是如何设计一个可以看做 O(1)O(1) 的求 gcd⁡\gcd 的方法了。
注意到对于一个数 VV 进行 nn 次 gcd⁡\gcd 运算，最多只会算 n+log⁡2Vn+\log_2 V 次。
考虑充分运用这个性质。
  • 对于上层节点，因为后面的前缀 gcd⁡\gcd 一定是前面的因数，所以我们记录上一次合并的区间 gcd⁡\gcd 直接用上，即可均摊 O(1)O(1)。
  • 对于下层节点，由于节点数不超过 log⁡2V\log_2 V，所以我们直接 O(nlog⁡V)O(n\log V) 预处理出每个点后 log⁡2V\log_2 V 个数的 gcd⁡\gcd，合并时直接 O(1)O(1) 使用。
总时间复杂度就是 O(nlog⁡V)O(n\log V) 的了。
CPP
#include <bits/stdc++.h>
namespace cjdst{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}
	
	int a[100005];
	int sufgcd[100005][31];
	std::unordered_map <int, ll> mp;
	
	std::vector <pii> get_pre(int l, int r){ 
		std::vector <pii> pre;
		for(int i = l; i <= r; i++){
			int len = pre.size() - 1;
			if(pre.empty()) pre.push_back({i, a[i]});
			else if(a[i] % pre[len].second == 0) pre[len].first = i;
			else pre.push_back({i, std::__gcd(a[i], pre[len].second)});
		}
		return pre;
	}
	
	std::vector <pii> get_suf(int l, int r){ 
		std::vector <pii> suf;
		for(int i = r; i >= l; i--){
			int len = suf.size() - 1;
			if(suf.empty()) suf.push_back({i, a[i]});
			else if(a[i] % suf[len].second == 0) suf[len].first = i;
			else suf.push_back({i, std::__gcd(a[i], suf[len].second)});
		}
		return suf;
	}
	
	void solve2(int l, int r){
		if(r - l + 1 <= 30){
			for(int i = l; i <= r; i++){
				for(int j = i; j <= r; j++){
					mp[sufgcd[i][j - i]]++;
				}
			}
			return;
		}
		int mid = (l + r) >> 1;
		solve2(l, mid);
		solve2(mid + 1, r);
		std::vector <pii> sl = get_suf(l, mid), pr = get_pre(mid + 1, r);
		for(int i = 0; i < int(sl.size()); i++){
			int curgcd = sl[i].second;
			ll len1 = mid - sl[i].first + 1;
			if(i) len1 -= mid - sl[i - 1].first + 1;
			for(int j = 0; j < int(pr.size()); j++){
				ll len2 = pr[j].first - mid;
				if(j) len2 -= pr[j - 1].first - mid;
				curgcd = std::__gcd(curgcd, pr[j].second);
				mp[curgcd] += len1 * len2;
			}
		}
	}

	void solve(){
		int n, m;
		std::cin >> n;
		for(int i = 1; i <= n; i++) std::cin >> a[i];
		for(int i = 1; i <= n; i++){
			sufgcd[i][0] = a[i];
			for(int j = 1; j <= 30; j++){
				if(i + j > n) break;
				sufgcd[i][j] = std::__gcd(sufgcd[i][j - 1], a[i + j]);
			}
		}
		solve2(1, n);
		std::cin >> m;
		while(m--){
			int val;
			std::cin >> val;
			std::cout << mp[val] << '\n';
		}
	}
}


int main(){
	cjdst::init();
	int T = 1;
	// std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

回复

共 7 条回复，欢迎继续交流。

正在加载回复...