约数之和
细节证明看我上一题的,在此只罗列公式
约数之和=(p1^0+p1^1+p2^2...+p1^x1)*(p2^0+p2^1+p2^2...+p2^x2)...*(pk^0+pk^1+pk^2...+pk^xk)
记起来就是从0-x1次方每一个p都算一遍然后相乘,看不懂就背板子。
强行解释一下:
拆分开来可以发现,每一项都是从p1->pk的某次方,且每一项各不相同,这些数其实就是把n的所有约数加到一起。
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int 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]++;//i的质因数指数+1
}
if(x>1)primes[x]++;
}
//以上过程完成primes就存了所有质因数的指数
LL res=1;
for(auto prime:primes)
{
int p=prime.first,a=prime.second;//用p来表示这个质数的底数,a来表示指数也就是p^a
LL t = 1;
while(a--) t=(t*p+1)%mod;
res=res*t%mod;
}
cout<<res<<endl;
return 0;
}
发现一个小错误
约数之和 = (p1^0 + p1^1 + p2^2 +…+ p1^x1)(p2^0 + p2^1 + p2^2 +…+ p2^x2) …*(pk^0 + pk^1 + pk^2 +…+ pk^xk)
感谢指正