AcWing 871. 约数之和 java
原题链接
简单
作者:
季之秋
,
2021-01-24 20:29:10
,
所有人可见
,
阅读 306
import java.util.*;
public class Main{
static HashMap<Integer,Integer> q=new HashMap<>();
public static void main(String[] args)throws Exception {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int INF=1000000007;
long ref=1;
while(n--!=0){
int x=sc.nextInt();
//p1^a1约数有p1^0、p2^1、p3^2 ………… p1^a1,有(a1+1)个数,然后每个因数之和相乘就是总约数之和
count(x);
}
for(int p:q.keySet()){
int a=q.get(p);
long sum=1;
while(a--!=0){
sum=(sum*p+1)%INF; //p1^a1=p1^0+p1^1+...+p1^a(约数和)
}
ref=ref*sum%INF; //因为乘积的约数可以=p1^a1 * p2^a2 * p3^a3...pn^an
//然后每个子因数的和相乘就是总和,long是因为INF的值是1e9超过int,%INF保证不超long的范围,
}
System.out.println(ref);
}
static void count(int n){//每一个子因数最小可以拆成哪些数相乘n转成p1^a1 * p2^a2 * p3^a3...pn^an的多项式
for(int i=2;i<=n/i;i++){
while(n%i==0) {
q.put(i,q.getOrDefault(i,0)+1);//相当于统计器,统计2--n每个约数的指数有多少
n/=i;
}
}
if(n>1) q.put(n,q.getOrDefault(n,0)+1);
}
}