c++ - c++中除数求和算法的实现

Question

我试图在 C++ 中实现除数求和算法，即

Let n = p1^a1 * p2^a2 * .... * pk^ak

Then

σ(n) = ( (p1^(a1+1) - 1) / (p1-1) ) * ( (p2^(a2+1) - 1) / (p2-1) ) * ... * ( (pk^(ak+1) - 1) / (pk-1) )

将因子插入 vector<int> p 的质数分解函数

void primeFactors(int n)
{
    while (n%2 == 0)
    {
        p.push_back(2);
        n = n/2;
    }
    for (ull i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            p.push_back(i);
            n = n/i;
        }
    }
    if (n > 2)
        p.push_back(n);
}

然后我创建一个 vector<int> p 的拷贝在 vector<int> pk作为vector<int> pk(p)并执行以下操作以在 p 中仅包含唯一元素。

auto it = unique(p.begin(),p.end());
 p.resize(distance(p.begin(),it) );

现在最后根据公式求和:

for(int i=0;i<p.size();i++){
        sum *= (pow(p[i],count(pk.begin(), pk.end(), p[i]))-1)/(p[i]-1);
    }

上面的实现是错误的，因为我没有得到正确的输出。我在哪里犯了错误？他们是更好的实现方法吗？

Answer 1

计算结果的最后一个循环是 pi^ai而不是 pi^(ai+1) .将其更改为:

for (int i = 0; i < p.size(); i++){
    sum *= (pow(p[i], count(pk.begin(), pk.end(), p[i]) + 1) - 1) / (p[i] - 1);
}

还有一件事，不是使用 vector 而是使用 unique和 count你可以简单地使用 map<int, int>而不是在 O(n) 中获取每个素数的出现次数，而是像这样在 O(lgn) 中获取它:

void primeFactors(int n, map<int, int> &facs){
    facs.clear();
    for (long long p = 2; p*p <= n; p++){
        while (n%p == 0){
            facs[p] ++;
            n /= p;
        }
    }
    if (n > 1)
        facs[n] = 1;
}

long long getRes(map<int, int> &facs){
    long long t, res = 1;
    for (auto it = facs.begin(); it != facs.end(); ++it){
        t = pow(it->first, it->second + 1) - 1;
        t /= (it->first - 1);
        res *= t;
    }
    return res;
}

在上面的代码中我还使用了pow计算结果的函数。我们可以通过在映射中存储功率值而不是计数来消除此函数，如下所示:

void primeFactors(int n, map<int, long long> &facs){
    facs.clear();
    for (long long p = 2; p*p <= n; p++){
        while (n%p == 0){
            if (facs.count(p))//this way we can save pi^(ai+1) instead of counting prime numbers
                facs[p] *= p;
            else
                facs[p] = p*p;
            n /= p;
        }
    }
    if (n > 1)
        facs[n] = n*n;
}

long long getRes(map<int, long long> &facs){
    long long t, res = 1;
    for (auto it = facs.begin(); it != facs.end(); ++it){
        t = it->second - 1;  //this is for pi^(ai+1)-1
        t /= (it->first - 1);
        res *= t;
    }
    return res;
}