AcWing 870. 约数个数-代码注释-golang
原题链接
简单
作者:
望哥
,
2020-07-17 19:02:28
,
所有人可见
,
阅读 527
package main
import "fmt"
import "bufio"
import "os"
var reader = bufio.NewReader(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)
const N = int(1e9)+7
var d = map[int]int{}
// 增加统计
func addPrimeExponent(i,c int){
if _,exist:=d[i];exist{
c+=d[i]
}
d[i] = c
}
// primes 统计质因数个数
func primes(a int) {
var cnt int
// 试除法 统计质因数及其个数
for i:=2;i<=a/i;i++{
if a%i == 0 {
cnt,a = 1, a/i
for a%i ==0 {
cnt++
a/=i
}
addPrimeExponent(i,cnt)
}
}
// 大于 sqrt(a) 大质因数只有一个
if a>1{
addPrimeExponent(a,1)
}
}
func main(){
var n,a int
fmt.Fscan(reader,&n)
for i:=0;i<n;i++{
fmt.Fscan(reader, &a)
// 统计质因数个数
primes(a)
}
res:=1 // 约数个数
for _,v:=range d{
res = (res*(v+1))%N
}
fmt.Println(res)
}