算法分析
基本思想:
如果 $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})$
while (b -- ) t = (t * a + 1) % mod;
$
t=t*p+1
$
$
t=1
$
$
t=p+1
$
$
t=p^2+p+1
$
$
…
$
$
t=p^b+p^{b-1}+…+1
$
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- )
{
int x;
cin >> x;
for (int i = 2; i <= x / i; i ++ )
while (x % i == 0)
{
x /= i;
primes[i] ++ ;
}
if (x > 1) primes[x] ++ ;
}
LL res = 1;
for (auto p : primes)
{
LL a = p.first, b = p.second;
LL t = 1;
while (b -- ) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
解释一下后面的哈希处理的那里,其实就是提取因子,类似于初中学的那个秦九韶算法
初中学过秦九韶😮
为什么t = (t * a + 1) % mod;中要加1呢?
其实你写一下就明白了,跟t初始值置1差不多
这个1可以认为是p^0
有个p的零次方要表示.而任何数(除了0)的0次方都是 1.
从结果出发,如果不加一结果就只有 p 的x次方,
你看一下秦九的那个算法就明白了,那里面就有1,是常数。 x^2 + x = x(x + 1);
因为有c1+1项,
按上述算法循环b次,最后可以生成所有质因子的幂次(p^b + p^b-1 + …… + 1)
秦九韶算法妙啊
# (p10+p11+…+p1c1)∗…∗(pk0+pk1+…+pkck)
大佬,不是说结果对mode取余嘛,为什么在这两个地方这样(t * a + 1) % mod; res = res * t % mod; cout << res << endl;在这输出res%mode就不对了呢
理论上先取模和后取模结果是一样的,但是这里后取模的话会导致中间结果溢出,就不能ac了
好的,谢谢大佬