对于约数之和我们需要知道1+…+a^n怎么计算,此处给出公式:x = (x * a + 1)进行计算。
C++ 代码
约数个数
对于任意一个合数,都可以写成质数相乘的形式。对于任意合数n,都有质因子1,
所以每个因子都是从0-a,共a+1个,,最后是当模后剩余的数为质数时,对该数的指数加1.
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int,int> hash;
while(n --)
{
int x;
cin >> x;
for(int i = 2;i <= x / i;i ++)//注意此时i从2开始是因为哈希表里存的是指数,1就是底数0次幂
{
while(x % i == 0)
{
hash[i] ++;
x /= i;
}
}
if(x > 1) hash[x] ++;
}
long long cnt = 1;//不用long,long会爆int
for(auto t : hash) cnt = cnt * (t.second + 1) % mod;
cout << cnt;
return 0;
}
约数之和
#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map<int,int> prime;
while(n --)
{
int x;
cin >> x;
for(int i = 2;i <= x / i;i ++)
{
while(x % i == 0)
{
prime[i] ++;
x /= i;
}
}
if(x > 1) prime[x] ++;
}
long long int res = 1;
for(auto t : prime)
{
int p = t.first,a = t.second;
long long int x = 1;//x爆int了......
//不能用等比数列求前n项来计算,因为指数可能会为0,此时使用sn=a1(1 - q^n) / (1 - q)会使分子为0
while(a --)
{
x = (x * p + 1) % mod;
}
res = (res * x) % mod;
}
cout << res;
}