c - 小于或等于N的数的除数之和

对于这个问题，我真的需要一些帮助：


  给定正整数N，我们将xsum(N)定义为所有小于或等于N的正整数除数的总和。
  
  例如：xsum（6）= 1 +（1 + 2）+（1 + 3）+（1 + 2 + 4）+（1 + 5）+（1 + 2 + 3 + 6）= 33。
  （xsum-1的除数之和+ 2的除数之和+ ... + 6的除法之和）
  
  给定正整数K，将要求您找到满足条件的最低N：xsum(N) >= K
  
  K是一个非零自然数，最多包含14位数字
  
  时限：0.2秒


显然，在超过“时限”的情况下，蛮力将下降。我还没有找到比它更好的东西，所以代码如下：

fscanf(fi,"%lld",&k);
i=2;
sum=1;
while(sum<k) {
    sum=sum+i+1;
    d=2;
    while(d*d<=i) {
          if(i%d==0 && d*d!=i)
             sum=sum+d+i/d;
          else
             if(d*d==i)
                 sum+=d;
           d++;
    }
    i++;
}

还有更好的主意吗？

最佳答案

对于范围[1，N]中的每个数字n，适用以下条件：n是范围[1，N]中的roundDown(N / n)精确数字的除数。因此，对于每个n，我们将总计n * roundDown(N / n)添加到结果中。

int xsum(int N){
    int result = 0;

    for(int i = 1 ; i <= N ; i++)
        result += (N / i) * i;//due to the int-division the two i don't cancel out

    return result;
}

与蛮力搜索相比，该算法背后的思想还可以用于更快地解决主问题（smallest N such that xsum(N) >= K）。

完整的搜索可以使用一些规则来进一步优化，这些规则可以从上面的代码中得出：K = minN * minN（如果minN，K = 2 * 3 * ...)将是正确的结果。使用此信息，我们可以进行下限搜索。

下一步将是搜索上限。由于xsum(N)的增长是（近似）平方的，因此我们可以使用它来近似N。这种优化的猜测可以非常快速地找到搜索到的值。

int N(int K){
    //start with the minimum-bound of N
    int upperN = (int) sqrt(K);
    int lowerN = upperN;

    int tmpSum;
    //search until xsum(upperN) reaches K
    while((tmpSum = xsum(upperN)) < K){
        int r = K - tmpSum;

        lowerN = upperN;
        upperN += (int) sqrt(r / 3) + 1;
    }

    //Now the we have an upper and a lower bound for searching N
    //the rest of the search can be done using binary-search (i won't
    //implement it here)

    int N;//search for the value

    return N;
}

关于c - 小于或等于N的数的除数之和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31762034/