利用算术基本定理求解约数个数|利用算术基本定理求解约数个数 + 约数之和
先前我们已经介绍过了怎么判断质数和约数，现在我们对于约数的个数和约数之和也要进行求解，而求解的方法就是根据算术基本定理来的！
先介绍一下什么是算术基本定理：
算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1*P2^a2*P3^a3......Pn^an，这里P1N 的标准分解式。
那么一直这个之后我们是不是可以知道这个自然数N的约数也是这样的形式D=P1^b1*P2^b2*P3^b3......Pn^bn，（0<=bn<=an），那么这样的话求解约数个数的问题就变化为了求组合数的问题了，就是高中的排列组合，所以约数个数即为（a1+1)(a2+1)(a3+1)……(an+1);
以下是代码：
#include
#define mod 1000000007
using namespace std;
typedef long long LL;
unordered_map
int main()
{
int n;
cin >> n;
LL ans = 1;
while (n -- )
{
int x;
cin >> x;
for(int i = 2;
i<=x/i;
i++){
while(x%i == 0) {
primes[i] ++ ;
x/=i;
}
}
if(x>1) primes[x] ++;
}
for(auto prime : primes) ans = ans * (prime.second + 1)%mod;
cout << ans << '\n';
return 0;
}
【利用算术基本定理求解约数个数|利用算术基本定理求解约数个数 + 约数之和】
那么这样的话我们再来看看约数之和怎么算，我们刚刚已经知道了约数的形式是这样的D=P1^b1*P2^b2*P3^b3......Pn^bn，所以所有的约数是不是相当于每个P1,P2,……Pn都出一个指数幂，然后求和；我们可以发现约数之和即为：（P1^0+P1^1+P1^2……+P1^a1)……（Pn^0+Pn^1+Pn^2……+Pn^a1);
接下来看代码：
#include
#define mod 1000000007
using namespace std;
typedef long long LL;
unordered_map
int main()
{
LL ans = 1;
int n;
cin >> n;
while (n -- )
{
int x;
cin >> x;
for(int i = 2;
i<=x/i;
i++){
while(x % i == 0){
primes[i] ++;
x/=i;
}
}
if(x > 1) primes[x] ++;
}
for(auto prime : primes) {
LL sum = 1;
LL p = 1;
for(int i = 1;
i<=prime.second;
i++){
sum = (sum*prime.first + 1)%mod;
}
ans = ans*sum%mod;
}
cout << ans << '\n';
return 0;
}
推荐阅读
- 数据结构与算法（C语言版）|【05_1数据结构】【算法入门_分治】二叉树初阶的基本理解、堆的概念及结构（含二叉树经典笔试题~）
- 初阶数据结构与算法|【初阶数据结构与算法】第七篇（二叉树和堆的基本概念+以及堆的实现）
- C/C++/C#|C++（Windows平台下利用LibTorch调用PyTorch模型）
- 由浅入深，从掌握Promise的基本使用到手写Promise
- #mysql|mysql--单表的数据查询
- 计算机系统|进程基本概念
- OpenCV利用手势识别实现虚拟拖放效果
- c语言实现图的基本操作--邻接矩阵存储|c语言实现图的基本操作--邻接矩阵存储,c语言实现图的基本操作--邻接矩阵存储...
- C#|从零开始手把手教你，.net 6用EF Core基本创建表，迁移到mysql数据库
- 如何利用Vue+Element做个小页面