专栏文章

U523244 题解

zzhujianheng
个人记录参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mint2vpq
此快照首次捕获于
2025/12/02 07:54
3 个月前
此快照最后确认于
2025/12/02 07:54
3 个月前
查看原文
注意到 Ai,AjA_i,A_j 必须是 AkA_k 的因数，考虑先 O(Vlog⁡V)O(V \log V) 存下所有可能的因数，用 vector 存下之后再考虑枚举 kk，然后枚举 AkA_k 的所有因数 xx，平均为 O(log⁡V)O(\log V) 个，然后再用 map 记录所有出现的数的位置，由于只有 10610^6，可以不用 map，用桶（但标程中用的 map，后来才知道可以爆标），然后每回求出 xx 和 Akx\dfrac{A_k}{x} 是否存在于数组 AA 中，如果存在，因为数组数互不相等，所以只要满足题目中的 1≤i<j<k≤n1 \le i < j < k \le n，就直接加 11，标程此部分时间复杂度 O(nlog⁡nlog⁡V)O(n \log n \log V) 的，但可以只用 O(nlog⁡V)O(n \log V) 完成。
时间复杂度 O((V+nlog⁡n)log⁡V)O((V+n \log n)\log V)，空间 O(n+Vlog⁡V)O(n+V \log V)，如果用桶的话时间 O((V+n)log⁡V)O((V+n) \log V)，空间 O(n+V+Vlog⁡V)O(n+V+V \log V)。
当然本题还有个 O(nlog⁡nV)O(n \log n \sqrt V) 的做法和一个 O(n3)O(n^3) 的暴力法，但不优，被我后来想到的 O(Vlog⁡V+nlog⁡nlog⁡V)O(V \log V+n \log n \log V) 给创飞了，然后又被 O((n+V)log⁡V)O((n+V) \log V) 给创飞了。
所以这题其实完全可以给 10610^6，卡双 log⁡\log。
懂了，下次出个加强版，同样的题解。
标程：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=200009,V=1000009;
int a[N];
vector<int> G[V];
map<int,int> mp;
void init(int n){
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j+=i)
			G[j].push_back(i);
}
int main(){
	ios::sync_with_stdio(0); 
	int n,v=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v=max(v,a[i]);
		mp[a[i]]=i;
	}
	init(v);
	long long ans=0;
	for(int k=1;k<=n;k++)
		for(int p=0;p<G[a[k]].size();p++){
			int x=G[a[k]][p];
			if(!mp[x]) continue;
			if(!mp[a[k]/x]) continue;
			if(mp[x]>mp[a[k]/x]||mp[a[k]/x]>k||mp[x]>k) continue;
			ans++;
		}
	cout<<ans<<endl;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...