[day 30] given an integer n, find the sum of its factors

This article has been included in the column 《Java Introduction 100 cases 》

order 、 Column Preface

   This column opens , The purpose is to help everyone better master learning Java, Especially some Java Learners' It is difficult to find systematic algorithm learning materials on the Internet to help you get started with algorithms , At the same time, if you have any questions about the contents of the column, you can add my wechat at the end of the article to give you a one-to-one explanation .
   But the most important thing is to think independently , For all the content of this column , Be able to fully master , Write the code completely by yourself , There must be no problem getting started with the algorithm .
   The learning of algorithm must not be short of summary , Here I recommend that you can go to University algorithm community Punch in the learned knowledge , To consolidate and review .
   The only way to learn algorithms well must be Topic sea strategy , Only by accumulating a lot of practice can you practice your skills . Any topic of the column I will start with 【 Title Description 】【 Their thinking 】【 Template code 】【 Code parsing 】 Wait for four plates to explain .

One 、【 Example 1】

1、 Title Description

   Given an integer $n(1\le n\le 1e9)$, Find the sum of its divisors , The answer is right $1e9+7$ modulus

2、 Their thinking

$(1)$ You can find the number of factors according to the code , Yes $O(n)$ and $O(\sqrt{n})$ Complex approach .
$(2)$ It can also be solved by the sum of approximations theorem , Focus on the theorem

3、 Template code

1） simple O(n) practice

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） Optimize root n practice

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) Sum of divisors theorem

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、 Code parsing

• $(1)$ I talked about it before. , For a positive integer $n$, From the basic theorem of the formula ：
  $$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}allbyqualityCount)$$
  So remember $n$ The sum of constraints is $f(n)$, Then there are ：
  $$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)$ prove :
  First calculate $p_1^{a_1}$ Sum of divisors of , It can be seen that $(p_1^0+p_1^1+...+p_1^{a_1})$
  Second, calculate $p_2^{a_2}$ Sum of divisors of , It can be seen that $(p_2^0+p_2^1+...+p_2^{a_2})$
  …
  Finally, I worked out $p_k^{a^k}$ Sum of divisors of , It can be seen that $(p_k^0+p_k^1+...+p_k^{a_k})$
  According to the principle of multiplication ,$n$ Sum of divisors of $f(n)by：$
  $$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})$$
  

Two 、【 Example 2】

1、 Title Description

   Given $n$ A positive integer $a_i$, Please output the sum of divisors of the product of these numbers , The answer is right $10^9+7$ modulus .

2、 Their thinking

$(1)$ On the last question , From the sum of the factors of a number to multiple numbers , But in essence, the final product is still a number .
$(2)$ We can $n$ All numbers are decomposed by prime factors , Count the total number of occurrences of each prime factor , Finally, use the sum of divisors theorem .

3、 Template code

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);
    }
    // Formula for finding prime factor 
    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);
    }
}

3、 ... and 、 Recommendation column

《 Zero fundamental algorithm 100 God 》

Four 、 After-school exercises

Serial number	Topic link	Difficulty rating
1	Sum of divisors	2

There are questions about learning ？