【第30天】给定一个整数 n ，求它的因数之和

本文已收录于专栏《Java入门一百例》

序、专栏前言

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

一、【例题1】

1、题目描述

  给定一个整数 $n(1\le n\le 1e9)$，求它的约数之和，答案对$1e9+7$取模

2、解题思路

$(1)$可以根据求因数个数的代码来求，有$O(n)$和$O(\sqrt{n})$复杂的做法。
$(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)$前面讲过，对于一个正整数$n$，由算式基本定理可得：
  $$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$的约束之和为$f(n)$,则有：
  $$f(n)=(p_1^0+p_1^1+...+p_1^{a_1})\ast (p_2^0+p_2^1+...+p_2^{a_2})\ast ...(p_k^0+p_k^1+...+p_k^{a_k})$$
• $(2)$证明:
  首先计算$p_1^{a_1}$的约数之和，可知为$(p_1^0+p_1^1+...+p_1^{a_1})$
  其次再算$p_2^{a_2}$的约数之和，可知为$(p_2^0+p_2^1+...+p_2^{a_2})$
  …
  最后算出$p_k^{a^k}$的约数之和，可知为$(p_k^0+p_k^1+...+p_k^{a_k})$
  根据乘法原理可得，$n$的约数之和$f(n)为：$
  $$f(n)=(p_1^0+p_1^1+...+p_1^{a_1})\ast (p_2^0+p_2^1+...+p_2^{a_2})\ast ...(p_k^0+p_k^1+...+p_k^{a_k})$$
  

二、【例题2】

1、题目描述

  给定 $n$ 个正整数 $a_i$，请你输出这些数的乘积的约数之和，答案对 $10^9+7$ 取模。

2、解题思路

$(1)$在上一题上，由一个数的因数之和拓展为多个数，但本质上乘积的最后仍然为一个数。
$(2)$我们可以将这$n$个数的都进行质因数的分解，统计每个质因数出现的总次数，最后使用约数之和定理即可。

3、模板代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    
    static final int mod = 1000000007;
    static Map<Integer, Integer> map = new HashMap<>();
    static long ans = 1;
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
    
            int a = sc.nextInt();
            getNums(a);
        }
        for (Integer a : map.keySet()) {
    
           long sum=1;
           int k=map.get(a);
           while(k-->0) sum=(sum*a+1)%mod;
           ans=(ans*sum)%mod;
        }
        System.out.print(ans);
    }
    //求质因数公式
    static void getNums(int n) {
    
        for (int i = 2; i <= n / i; i++) {
    
            while (n % i == 0) {
    
                map.put(i, map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if (n > 1) map.put(n, map.getOrDefault(n, 0) + 1);
    }
}

三、推荐专栏

《零基础学算法100天》

四、课后习题

序号	题目链接	难度评级
1	约数求和	2

学习有疑问？