学习指引
- 序列，专栏前言
- 一、【例题1】
-
- 1、题目描述
- 2、解题思路
- 3、模板代码
-
- 1）朴素O(n)做法
- 2)优化根号n做法
- 3)约数之和定理
- 4、代码解析
- 二、【例题2】
-
- 1、题目描述
- 2、解题思路
- 3、模板代码
- 三、推荐专栏
- 四、课后练习
序列，专栏前言
?? 本专栏的目的是帮助您更好地掌握和学习Java，特别是一些Java学习者网上很难找到系统的算法学习资料来帮助自己进入算法， ?? 但最重要的是要独立思考。如果能完全掌握本专栏的所有内容，完全写代码，算法入门肯定没问题。 ?? 算法的学习不能缺少总结。在这里，我建议你可以在大学算法社区打卡你所学的知识，以巩固和复习。 ??学好算法的唯一途径一定是，只有积累大量的练习，养一种技能。我将从四个部分解释专栏中的任何主题，如主题描述解决方案模板代码代码分析。
一、【例题1】
1、题目描述
??给定一个整数 n ( 1 ≤ n ≤ 1 e 9 ) n(1\leq n\leq1e9) n(1≤n≤1e9)，答案对 1 e 9 7 1e9 7 1e9 7取模
2、解题思路
( 1 ) (1) (1)可以根据求因数的代码来求，有 O ( n ) O(n) O(n)和 O ( n ) O(\sqrt n) O(n )复杂的做法。 ( 2 ) (2) (2)也可以约数之和定理求解，重点讲解该定理
3、模板代码
1）朴素O(n)做法
import java.util.*;
public class Main {
static int mod=1000000007;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long ans=0;
for (int i = 1; i <=n; i++) {
if (n%i==0) ans=(ans+i)%mod;
}
System.out.println(ans);
}
}
2）优化根号n做法
import java.util.*;
public class test {
static int mod=1000000007;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long ans=0;
for (int i = 1; i <=n/i; i++) {
if (n%i==0){
if (i!=n/i){
ans=(ans+i)%mod;
ans=(ans+n/i)%mod;
}else{
ans=(ans+i)%mod;
}
}
}
System.out.println(ans);
}
}
3)约数之和定理
import java.util.*;
public class test {
static int mod=1000000007;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long sum=1;
for (int i = 2; i <=n/i; i++) {
if (n%i==0){
int c=0;
while (n%i==0){
c++;
n/=i;
}
long t=1;
while (c-->0) t=(t*i+1)%mod;
sum=(sum*t)%mod;
}
}
if (n>1) sum=(sum*(n+1)%mod);
System.out.println(sum);
}
}
4、代码解析
- ( 1 ) (1) (1)前面讲过，对于一个正整数 n n n，由算式基本定理可得： n = ∏ i = 1 k p i i = p 1 a 1 × p 2 a 2 × p 3 a 3 . . . . . . p k a k ( p 1 , p 2 . . . . p k 均 为 质 数 ) n=\prod_{i=1}^{k} p_i^{^i}=p_1^{a^1}\times p_2^{a^2}\times p_3^{a^3}......p_k^{a^k}(p_1,p_2....p_k均为质数) n=i=1∏kpii=p1a1×p2a2×p3a3......pkak(p1,p2....pk均为质数) 那么记 n n n的约束之和为 f ( n ) f(n) f(n),则有： f ( n ) = ( p 1 0 + p 1 1 + . . . + p 1 a 1 ) ∗ ( p 2 0 + p 2 1 + . . . + p 2 a 2 ) ∗ . . . ( p k 0 + p k 1 + . . . + p k a k ) f(n)=(p_1^0+p_1^1+...+p_1^{a_1})*(p_2^0+p_2^1+...+p_2^{a_2})*...(p_k^0+p_k^1+...+p_k^{a_k}) f(n)=(p10+p11+...+p1a1)∗(p20+p21+...+p2a2)∗...(pk0+pk1+...+pkak)
- ( 2 ) (2) (2)证明: 首先计算 p 1 a 1 p_1^{a_1} p1a1的约数之和，可知为 ( p 1 0 + p 1 1 + . . . + p 1 a 1 ) (p_1^0+p_1^1+...+p_1^{a_1}) (p10+p11+...+p1a1) 其次再算 p 2 a 2 p_2^{a_2} p2a2的约数之和，可知为 ( p 2 0 + p 2 1 + . . . + p 2 a 2 ) (p_2^0+p_2^1+...+p_2^{a_2}) (p20+p21+...+p2a2) … 最后算出 p k a k p_k^{a^k} pkak的约数之和，可知为 ( p k 0 + p k 1 + . . . + p k a k ) (p_k^0+p_k^1+...+p_k^{a_k}) (pk0+pk1+...+pkak) 根据乘法原理可得， n n n的约数之和 f ( n ) 为 ： f(n)为： f( 标签： pk1接近传感器sc1204