AcWing 871题约数之和的解法是什么？
- 内容介绍
- 文章标签
- 相关推荐
本文共计248个文字，预计阅读时间需要1分钟。
题目+思路+约数之和定理+公式：设\( s(n) \)为\( n \)的约数之和，公式为：\[ s(n)=(p_1^0 + p_1^1 + ... + p_1^{a_1})(p_2^0 + p_2^1 + ... + p_2^{a_2})... (p_k^0 + p_k^1 + ... + p_k^{a_k}) \]
题目
思路
- 由约数之和定理可知约数之和公式为：$s(n) = ({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})({p_2}^0 + {p_2}^1 + ... + {p_2}^{a_2})...({p_k}^0 + {p_k}^1 + ... + {p_k}^{a_k})$
- 计算 $({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})$ 可用秦九韶算法
LL t = 1;
while (x -- ) t = (t * p + 1) % mod;
代码
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;
int main()
{
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 prime:primes)
{
LL p = prime.first, x = prime.second;
LL t = 1;
while (x -- ) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
本文共计248个文字，预计阅读时间需要1分钟。
题目+思路+约数之和定理+公式：设\( s(n) \)为\( n \)的约数之和，公式为：\[ s(n)=(p_1^0 + p_1^1 + ... + p_1^{a_1})(p_2^0 + p_2^1 + ... + p_2^{a_2})... (p_k^0 + p_k^1 + ... + p_k^{a_k}) \]
题目
思路
- 由约数之和定理可知约数之和公式为：$s(n) = ({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})({p_2}^0 + {p_2}^1 + ... + {p_2}^{a_2})...({p_k}^0 + {p_k}^1 + ... + {p_k}^{a_k})$
- 计算 $({p_1}^0 + {p_1}^1 + ... + {p_1}^{a_1})$ 可用秦九韶算法
LL t = 1;
while (x -- ) t = (t * p + 1) % mod;
代码
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int n;
int main()
{
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 prime:primes)
{
LL p = prime.first, x = prime.second;
LL t = 1;
while (x -- ) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}