algorithm - 查找范围内的 mod 操作的总和

如果我们有 2 个数字，比如说 a and b 那么我们如何找到 sum of b%i where i ranges from 1 to a 的值？
一种方法是遍历从 1 到 a 的所有值，但有什么有效的方法吗？
(比 O(n) 好？)
例如:如果 a = 4 且 b = 5 那么需要 ans = 5%1+5%2+5%3+5%4=4
谢谢。

最佳答案

对于 i > b ，我们有 b % i == b ，所以总和的一部分很容易在恒定时间内计算( (a-b)*b ，如果 a >= b ，否则为 0 )。
i <= b 的部分还有待计算(i == b 为 0，因此可以忽略)。你可以在 O(sqrt(b)) 步骤中做到这一点，

对于 i <= sqrt(b) ，计算 b % i 并添加到总和

对于 i > sqrt(b) ，让 k = floor(b/i) ，然后是 b % i == b - k*i 和 k < sqrt(b) 。所以对于 k = 1 到 ceiling(sqrt(b))-1 ，让 hi = floor(b/k) 和 lo = floor(b/(k+1)) 。有 hi - lo 数 i 使得 k*i <= b < (k+1)*i ，它们的 b % i 之和是 sum_{ lo < i <= hi } (b - k*i) = (hi - lo)*b - k*(hi-lo)*(hi+lo+1)/2 。

如果 a <= sqrt(b) ，则仅适用第一个项目符号，在 a 处停止。如果 sqrt(b) < a < b ，在第二个项目符号中，从 k = floor(b/a) 运行到 ceiling(sqrt(b))-1 并将最小 k 的上限调整为 a 。

总体复杂度 O(min(a,sqrt(b)))。

代码(C):

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

unsigned long long usqrt(unsigned long long n);
unsigned long long modSum(unsigned long long a, unsigned long long b);

int main(int argc, char *argv[]){
    unsigned long long a, b;
    b = (argc > 1) ? strtoull(argv[argc-1],NULL,0) : 10000;
    a = (argc > 2) ? strtoull(argv[1],NULL,0) : b;
    printf("Sum of moduli %llu %% i for 1 <= i <= %llu: %llu\n",b,a,modSum(a,b));
    return EXIT_SUCCESS;
}

unsigned long long usqrt(unsigned long long n){
    unsigned long long r = (unsigned long long)sqrt(n);
    while(r*r > n) --r;
    while(r*(r+2) < n) ++r;
    return r;
}

unsigned long long modSum(unsigned long long a, unsigned long long b){
    if (a < 2 || b == 0){
        return 0;
    }
    unsigned long long sum = 0, i, l, u, r = usqrt(b);
    if (b < a){
        sum += (a-b)*b;
    }
    u = (a < r) ? a : r;
    for(i = 2; i <= u; ++i){
        sum += b%i;
    }
    if (r < a){
        u = (a < b) ? a : (b-1);
        i = b/u;
        l = b/(i+1);
        do{
            sum += (u-l)*b;
            sum -= i*(u-l)*(u+l+1)/2;
            ++i;
            u = l;
            l = b/(i+1);
        }while(u > r);
    }
    return sum;
}

关于algorithm - 查找范围内的 mod 操作的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9315273/