所以说求一个数所有因数也是根号分治?
  • 板块学术版
  • 楼主Muse_Dash
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/5/5 17:49
  • 上次更新2024/5/5 20:35:31
查看原帖
所以说求一个数所有因数也是根号分治?
776633
Muse_Dash楼主2024/5/5 17:49

给定一个数 nn,求其所有因数的集合,n≤1012n\leq10^{12}。

显然有 Θ(n)\Theta(\sqrt n) 的做法。

那是不是也可以这么理解:

对于因数 x≤nx\leq\sqrt n,枚举 xx 即可。

对于因数 x>nx>\sqrt n,由于 x∣nx\mid n,也就有 nx∣n\frac{n}{x}\mid n,枚举 nx\frac{n}{x} 即可。

可能这种理解方式挺若只的

2024/5/5 17:49
加载中...