时间戳

首页 > 解决方案 > 求和的速度问题（除数之和）

c++ - 求和的速度问题（除数之和）

问题描述

我应该在 C++ 中实现这个求和。我已经尝试过使用这段代码，但是对于高达 10 ^ 12 的数字来说，它需要的时间太长了。

总结是：求和

对于任何正整数 k，令 d(k) 表示 k 的正除数的数量（包括 1 和 k 本身）。例如，对于数字 4：1 有 1 个除数，2 有两个除数，3 有两个除数，4 有三个除数。所以结果是 8。

这是我的代码：

#include <iostream>
#include <algorithm>

using namespace std;

int findDivisors(long long n) 
{
    int c=0;
    for(int j=1;j*j<=n;j++)
    {
        if(n%j==0)
        {
            c++;
            if(j!=(n/j))
            {
                c++;
            }
        }
    }
    return c;
}

long long compute(long long n)
{
    long long sum=0;
    for(int i=1; i<=n; i++)
    {
        sum += (findDivisors(i));
    }
    return sum;
}

int main()
{
    int n, divisors;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n;

    cout << compute(n);
}

我认为这不仅仅是一个简单的优化问题，也许我应该完全改变算法。有人有什么想法可以加快速度吗？谢谢你。

标签： c++c++11

解决方案

我使用您的蛮力方法作为参考来拥有测试用例。我用的是

compute(12) == 35
cpmpute(100) == 482

不要对计算分解感到困惑。在分解数字时可以玩一些技巧，但实际上你不需要任何技巧。解决方案是一个简单的O(N)循环：

#include <iostream>
#include <limits>

long long compute(long long n){
    long long sum = n+1;
    for (long long i=2; i < n ; ++i){
        sum += n/i;
    }
    return sum;
}

int main()
{
    std::cout << compute(12) << "\n";
    std::cout << compute(100) << "\n";
}

输出：

35
482

为什么这行得通？

关键在于 Marc Glisse 的评论：

与这类问题一样，这个总和实际上计算对 x, y，其中 x 除以 y，并且总和被安排为首先计算与固定 y 相对应的所有 x，但没有什么说你必须保持这种方式。

我可以在这里停下来，因为评论已经解释了一切。不过，如果它还没有点击...

诀窍是要意识到计算所有数字的除数要简单得多，n而不是n计算单个数字的除数并求和。

您无需关心 eg 的因式分解123123123或52323423将所有除数计数为10000000000. 你所需要的只是改变观点。与其尝试分解数字，不如考虑除数。除数多久1出现一次n？很简单：-n次。除数多久2出现一次？仍然很简单：n/2次，因为每一秒的数字都可以被 整除2。除数3？每第三个数都可以被 整除3。我希望你已经可以看到模式了。

您甚至可以将循环减少到只循环 until n/2，因为更大的数字显然只作为除数出现一次。虽然我没有费心去更进一步，因为最大的变化是从你的O(N * sqrt(N))到O(N).

推荐阅读