AcWing 871. 约数之和-代码注释-golang
原题链接
简单
作者:
望哥
,
2020-07-17 19:49:24
,
所有人可见
,
阅读 747
package main
import "fmt"
import "bufio"
import "os"
var reader = bufio.NewReader(os.Stdin)
var writer = bufio.NewWriter(os.Stdout)
const N = uint64(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)
}
// 约数之和
// 数 a 质因数分解后形如下:
// a = p1^e1 * p2^e2 * p3^e3 ... * pn^en
// 约数个数: (e1+1)*(e2+1)*(e3+1) ... *(en+1)
// 每一个质因数取不同的值,进行组合,有多少种组合就有多少个约数
// 约数之和: (p1^0 + p1^1 ... p1^e1) * (p2^0 + p2^1 ... + p2^e2) ... * (pn^0 + pn^1 + ...+ pn^en)
// 以上多项式展开后每一个组合就是一个约数
var res uint64 = 1
for k,v:=range d{
var t uint64 = 1
for i:=0;i<v;i++{
t = ((t*uint64(k))+1) % N
}
res = (res* t) %N
}
fmt.Println(res%N)
}