约数之和
题目 约数之和
思路分析
沿用上一题的思想
把一个数N 写成：\(N = (p1^{x1})(p2^{x2})(p3^{x3})…(pk^{xk})\)，其中pi为质数。
则N的约数个数为：\((x1+1)(x2+1)(x3+1)…(xk+1)\)
那这N个约数的和其实就是(\(p1^0+p1^1+……+p1^{x1})……(Pk^0+pk^1+……+pk^{xk})\)
还是拿这个例子
例如：12 的质因子有 2，3 12的约数有：1，2，3，4，6，12
约数1 是由 0 个 2， 0 个3相乘得到的
约数2 是由 1 个 2， 0 个3相乘得到的
约数3 是由 0 个 2， 1 个3相乘得到的
约数4 是由 2 个 2， 0 个3相乘得到的
约数6 是由 1 个 2， 1 个3相乘得到的
约数12 是由 2 个 2， 1 个3相乘得到的
12 可以分解为：\(2^2*3^1\)
那么约数之和 应该是\((2^0+2^1+2^2)(3^0+3^1)=7*4=28\)
等价于 1+2+3+4+6+12=28
证明：
记忆的话
先拆出所有质因数
对每一个基数都从 0到指数 累加一遍 然后相乘
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
unordered_map<int,int> weight;
int T;
int main()
{
cin>>T;
while(T--){
int n;cin>>n;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1)
weight[n]++;
}
LL res=1;
for(auto prime:weight){
int base=prime.first,index=prime.second;
LL temp=1,sum=1;
while(index--){
temp=temp*base%mod;
sum=(sum+temp)%mod;
}
res=res*sum%mod;
}
cout<<res;
return 0;
}
//直观一点 有个pow函数算指数
LL res=1;
for(auto prime:weight){
int base=prime.first,index=prime.second;
LL sum=0;
for(int i=0;i<=index;i++){
sum=(sum+pow(base,i))%mod;//报错
}
res=res*sum%mod;
}
/*
sum=(sum+pow(base,i))%mod;
| ~~~~~~~~~~~~~~~~~^~~~
| | |
| | const int
| __gnu_cxx::__promote_2<int, int, double, double>::__type {aka double}
*/
//pow函数返回一个 double 类型的结果，与 mod（一个 int 类型）进行取模会冲突
//C++ 中没有为浮点数定义取模运算符 %
//要改进的话 其实就可以牵扯到快速幂算法了 (负改进emm）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
unordered_map<int,int> weight;
int T;
// 快速幂算法，计算 (base^exponent) % mod
LL modPow(LL base, LL exponent, LL modulus) {
base %= modulus;
LL result = 1;
while (exponent > 0) {
if (exponent % 2 == 1)
result = (result * base) % modulus;
base = (base * base) % modulus;
exponent >>= 1;
}
return result;
}
int main()
{
cin>>T;
while(T--){
int n;cin>>n;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1)
weight[n]++;
}
LL res=1;
for(auto prime:weight){
int base=prime.first,index=prime.second;
LL sum=0;
for(int i=0;i<=index;i++){
sum = (sum + modPow(base, i, mod)) % mod;
}
res=res*sum%mod;
}
cout<<res;
return 0;
}
//还有一种好像说是秦九韶算法 temp*base+1
//不太清楚怎么来的
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
unordered_map<int,int> weight;
int T;
int main()
{
cin>>T;
while(T--){
int n;cin>>n;
for(int i=2;i<=n/i;i++){
while(n%i==0){
weight[i]++;
n/=i;
}
}
if(n>1)
weight[n]++;
}
LL res=1;
for(auto prime:weight){
int base=prime.first,index=prime.second;
LL temp=1;
while(index--){
temp=(temp*base+1)%mod;
}
res=res*temp%mod;
}
cout<<res;
return 0;
}
chatgpt:
这段代码利用了累加和乘法的性质来计算形如1+a+a2+…+an的表达式的结果模一个数（这里是模1e9+7）。
这并不是秦九韶算法，而是一种利用模运算和幂运算性质的方法。让我们分步骤解析这个计算过程。
素数分解和权重
首先，对于输入的每个数n，代码通过素数分解的方式计算每个素数的幂次（权重）。素数分解是将一个数表示为几个素数的乘积，每个素数可能被重复使用。在代码中，这通过循环除以素数并增加该素数权重的方式来实现。
计算1+a+a2+…+an模mod
接下来，对于每个素数及其权重，代码计算形如1+a+a2+…+an的表达式的模mod结果。这个计算过程使用了一个累加器`temp`，初始值为1（因为最开始有一个1），然后对于每个素数的每个幂次，累加器乘以基数`base`并加1，每次操作后取模以避免溢出。
这种方法的关键在于，它直接在累加过程中应用了模运算，这样可以保证结果始终在模mod的范围内。这种方法非常高效，因为它避免了大数的直接幂运算和直接求和，而是在每一步都进行了模运算。
结果的累乘
最后，所有这些1+a+a2+…+an模mod的结果被累乘起来（也即，对于每个素数分解出的基数及其权重，计算的结果相乘），得到最终的结果。这一步同样每次操作后都取模，确保最终结果在模mod的范围内。
总结
这段代码之所以能够工作，是因为它巧妙地利用了模运算的性质，在计算过程中保持了数值的规模，从而避免了大数操作可能带来的问题。虽然这不是秦九韶算法，但它是一个有效利用数学性质和计算机算法来解决特定问题的例子。秦九韶算法是古代中国数学家秦九韶发明的一种多项式的算术求解方法，主要用于简化多项式的计算，其核心思想是“开方法”和“正负相消”，在处理多项式运算方面非常有效，但与这段代码实现的计算任务性质不同。
💬 评论