найти сумму операций мода в диапазоне

Question

если у нас есть 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 Спасибо.

Answer 1

Для 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 (мин (а, квт)(б))).

Код (С):

#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;
}