算法解析
1:先对每个数进行分解质因数,然后用map统计质因数出现的次数,所有数的质因数次数会叠加在一起
2:再利用公式进行相乘
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)
一看见这个公式是一脸懵的,其实第一个公式就是我们之前学的分解质因数的公式,下面会举一个实例来证明
不懂的话带进实例就清晰很多了
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 = 1l;
for(Integer a : map.keySet()) res = res * (map.get(a) + 1) % 1000000007;
System.out.print(res);
}
}
实例好评 感谢大佬
可以,比前面的写的到位
哥们 最后统计个数的时候 有点问题
P1^c1的约数个数 应该是c1+1个吧?