约数 - 版本历史

Rmolives：/* 实现 */

2022-02-24T07:45:56Z

实现

←上一版本		2022年2月24日 (四) 15:45的版本
第17行：		第17行：
	int m;		int m;
	void divisor_factor(int n) {		void divisor_factor(int n) {
	for (int i = 0; i*i <= n; ++i) {		for (int i = 0; i * i <= n; ++i) {
	if (n % i == 0) {		if (n % i == 0) {
	f[++m] = i;		f[++m] = i;

Rmolives：/* 实现 */

2022-02-24T07:45:45Z

实现

←上一版本		2022年2月24日 (四) 15:45的版本
第17行：		第17行：
	int m;		int m;
	void divisor_factor(int n) {		void divisor_factor(int n) {
	for (int i = 0; i <= ~~sqrt(~~n); ++i) {		for (int i = 0; i*i <= n; ++i) {
	if (n % i == 0) {		if (n % i == 0) {
	f[++m] = i;		f[++m] = i;

2022年2月22日 (二) 08:55 Rmolives

2022-02-22T08:55:31Z

←上一版本		2022年2月22日 (二) 16:55的版本
第2行：		第2行：

	== 算数基本定理的推论 ==		== 算数基本定理的推论 ==
	~~在算数基本定理中，若正整数N被唯一分解为~~<math>N = \prod_{i=1}^m p_i^{c_i}</math>，其中 <math>c_i</math> 都是正整数，<math>p_i</math> 都是素数，且满足 <math>p_1<p_2<\cdots <p_m</math> ，则N的正约数集合可写作：<math>\{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\}</math> , 其中 <math>0 \leq b_i \leq c_i</math>		在[[算数基本定理]]中，若正整数N被唯一分解为<math>N = \prod_{i=1}^m p_i^{c_i}</math>，其中 <math>c_i</math> 都是正整数，<math>p_i</math> 都是素数，且满足 <math>p_1<p_2<\cdots <p_m</math> ，则N的正约数集合可写作：<math>\{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\}</math> , 其中 <math>0 \leq b_i \leq c_i</math>

	N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>		N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>
第9行：		第9行：

	== 实现 ==		== 实现 ==
	求N的正约数集合，若 <math>d \geq \sqrt N</math> 是N的约数，则 <math>\frac{N}{d} \leq \sqrt N</math> ~~也是N的约数。、~~		求N的正约数集合，若 <math>d \geq \sqrt N</math> 是N的约数，则 <math>\frac{N}{d} \leq \sqrt N</math> 也是N的约数。

	因此，只需要扫描 <math>d=1 \backsim \sqrt N</math> 尝试d能否整除N，若能整除，则 <math>\frac{N}{d}</math> 也是N的约数。时间复杂度为<math>O(\sqrt N)</math> 。		因此，只需要扫描 <math>d=1 \backsim \sqrt N</math> 尝试d能否整除N，若能整除，则 <math>\frac{N}{d}</math> 也是N的约数。时间复杂度为<math>O(\sqrt N)</math> 。

Rmolives：/* 实现 */

2022-02-22T08:36:08Z

实现

←上一版本		2022年2月22日 (二) 16:36的版本
第16行：		第16行：
	int f[MAX_N];		int f[MAX_N];
	int m;		int m;
	void divisor_factor(~~inr~~ n) {		void divisor_factor(int n) {
	for (int i = 0; i <= sqrt(n); ++i) {		for (int i = 0; i <= sqrt(n); ++i) {
	if (n % i == 0) {		if (n % i == 0) {

2022年2月22日 (二) 08:35 Rmolives

2022-02-22T08:35:52Z

←上一版本		2022年2月22日 (二) 16:35的版本
第26行：		第26行：
	}		}
	</syntaxhighlight>		</syntaxhighlight>

			== 参考资料 ==
			# 算法竞赛进阶指南，李煜东，139页
			[[Category:数学]]

2022年2月22日 (二) 08:35 Rmolives

2022-02-22T08:35:18Z

←上一版本		2022年2月22日 (二) 16:35的版本
第7行：		第7行：

	N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math>		N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math>

			== 实现 ==
			求N的正约数集合，若 <math>d \geq \sqrt N</math> 是N的约数，则 <math>\frac{N}{d} \leq \sqrt N</math> 也是N的约数。、

			因此，只需要扫描 <math>d=1 \backsim \sqrt N</math> 尝试d能否整除N，若能整除，则 <math>\frac{N}{d}</math> 也是N的约数。时间复杂度为<math>O(\sqrt N)</math> 。

			<syntaxhighlight lang="c" line>
			int f[MAX_N];
			int m;
			void divisor_factor(inr n) {
			for (int i = 0; i <= sqrt(n); ++i) {
			if (n % i == 0) {
			f[++m] = i;
			if (i != n/i)
			f[++m] = n/i;
			}
			}
			}
			</syntaxhighlight>

2022年2月22日 (二) 08:26 Rmolives

2022-02-22T08:26:31Z

←上一版本		2022年2月22日 (二) 16:26的版本
第6行：		第6行：
	N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>		N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>

	N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}]</math>		N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math>

2022年2月22日 (二) 08:26 Rmolives

2022-02-22T08:26:23Z

←上一版本		2022年2月22日 (二) 16:26的版本
第6行：		第6行：
	N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>		N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>

	N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}]</math>		N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}]</math>

2022年2月22日 (二) 08:25 Rmolives

2022-02-22T08:25:56Z

←上一版本		2022年2月22日 (二) 16:25的版本
第6行：		第6行：
	N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>		N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>

	N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i}{{p_i}^j}]</math>		N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}]</math>

2022年2月22日 (二) 08:25 Rmolives

2022-02-22T08:25:22Z

←上一版本		2022年2月22日 (二) 16:25的版本
第1行：		第1行：
	~~。若整数n除以整数d的余数为0，即d能整除n，则称d是n的~~'''约数'''，n是d的'''倍数'''，记为 <math>d\|n</math> 。		若整数n除以整数d的余数为0，即d能整除n，则称d是n的'''约数'''，n是d的'''倍数'''，记为 <math>d\|n</math> 。

			== 算数基本定理的推论 ==
			在算数基本定理中，若正整数N被唯一分解为<math>N = \prod_{i=1}^m p_i^{c_i}</math>，其中 <math>c_i</math> 都是正整数，<math>p_i</math> 都是素数，且满足 <math>p_1<p_2<\cdots <p_m</math> ，则N的正约数集合可写作：<math>\{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\}</math> , 其中 <math>0 \leq b_i \leq c_i</math>

			N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math>

			N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i}{{p_i}^j}]</math>

约数 - 版本历史

Rmolives：​/* 实现 */

Rmolives：​/* 实现 */

2022年2月22日 (二) 08:55 Rmolives

Rmolives：​/* 实现 */

2022年2月22日 (二) 08:35 Rmolives

2022年2月22日 (二) 08:35 Rmolives

2022年2月22日 (二) 08:26 Rmolives

2022年2月22日 (二) 08:26 Rmolives

2022年2月22日 (二) 08:25 Rmolives

2022年2月22日 (二) 08:25 Rmolives

Rmolives：/* 实现 */

Rmolives：/* 实现 */

Rmolives：/* 实现 */