算法解析

这道题虽然代码短，但是包含了很多的知识点，包括分解质因子，秦九韶算法，hashmap的熟练使用，如果一个知识点没弄懂，那这道题就会做不出来

HashMap有趣的知识点

HashMap<> 的泛型中只能存储包装类，不能存储基本数据类型 

map.keySet()             //以set的形式返回所有的key [2,3,5]

map.getOrDefault(i,0);   //如果i有value的话，就获取i的value，否则就默认value为0

公式证明

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

一看见这个公式是一脸懵的，其实第一个公式就是我们之前学的分解质因数的公式，下面会举一个实例来证明

不懂的话带进实例就清晰很多了

算法思想

1：先对每个数进行分解质因数，然后用map统计质因数出现的次数，所有数的质因数次数会叠加在一起

2：再利用公式进行相乘

java代码

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

public class Main{
    static Map<Integer,Integer> map = new HashMap<>();

    public static void main(String[] args){
        Scanner in  =new Scanner(System.in);

        int n = in.nextInt();

        while(n -- > 0)
        {
            int x = in.nextInt();

            for(int i = 2; i <= x / i; i ++)
            {
                while(x % i == 0)
                {
                    x /= i;
                    map.put(i, map.getOrDefault(i,0) + 1);
                }
            }

            if(x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
        }

        long res = 1;
        for(Integer a : map.keySet())
        {
            int b = map.get(a);
            long t = 1;
            while(b-- > 0) t = (t * a + 1) % 1000000007;
            res = res * t % 1000000007;
        }
        System.out.print(res);
    }
}