社区讨论

整除分块套 powerful number 筛

4401rk8
学术版参与者 5已保存回复 18

讨论操作

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

当前回复
18 条
当前快照
1 份
快照标识符
@lo8rdh34
此快照首次捕获于
2023/10/27 23:18
2 年前
此快照最后确认于
2023/10/27 23:18
2 年前
查看原帖
代码大概长这样：
CPP
// p 是质数集
void dfs(LL n,int i,LL x) {
	LL y = n/x;
	for(; p[i]*p[i] <= y; ++i)
		for(LL pp = p[i]*p[i], e = 2; pp <= y; pp *= p[i], ++e)
			dfs(n,i+1,x*pp);
}
for(LL l = 1, x,r; l <= n; l = r+1)
	x = n/l, r = n/x, dfs(r,0,1,1)
求证复杂度，跑下来类似 O(n45)O(n^{\frac{4}{5}})
模拟赛题解 说可以做到 O(n23)O(n^{\frac{2}{3}})（可能是我理解错了），是不是有什么高明的做法

回复

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

正在加载回复...