发现的范围内模运算的总和

问题描述

如果我们有2个数字，说 a和b 那么，我们如何才能找到的B％总和其中i从1范围值到？一种方式是通过从1所有的值迭代到但没有任何有效的方法？（为O更好的（N）？）如：如果一个= 4和b = 5则需要ANS = 5％1 + 5％2 + 5％3 + 5％4 = 4谢谢你。

if we have 2 numbers, say a and b then how can we find the value of sum of b%i where i ranges from 1 to a?One way is to iterate through all values from 1 to a but is there any efficient method?(better than O(n) ?)E.g : if a = 4 and b = 5 then required ans = 5%1+5%2+5%3+5%4=4Thanks.

推荐答案

有关 I＆GT; b ，我们 B％我== b ，使之和的那部分很容易计算在固定时间内（ （AB）* B ，如果 A＆GT; = B ，否则为0）

For i > b, we have b % i == b, so that part of the sum is easily calculated in constant time ((a-b)*b, if a >= b, 0 otherwise).

部分的 I＆LT; = B 还有待计算（我== b 给出0，从而可以忽略）。你可以这样做，在O（开方（B））步骤，

The part for i <= b remains to be calculated (i == b gives 0, thus may be ignored). You can do that in O(sqrt(b)) steps,

• 为 I＆LT; =开方（B），计算 B％I 并添加总结
• 为 I＆GT;开方（B），让 K =楼（B / I），然后 B％I = = b - K * I 和 K＆LT;开方（B）。因此，对于 K = 1 到上限（开方（B）） - 1 ，让喜=楼（B / K）和 LO =楼（B /（K + 1））。有喜 - 罗号我，使得 K * I＆LT; = B＆LT; （K + 1）* I 的 B％I 对他们来说是 sum_ {LO＆LT的总和; I＆LT; =喜}（B - K * I）=（HI - LO）* B - K *（HI-LO）*（HI + LO + 1）/ 2

• For i <= sqrt(b), calculate b % i and add to sum
• For i > sqrt(b), let k = floor(b/i), then b % i == b - k*i, and k < sqrt(b). So for k = 1 to ceiling(sqrt(b))-1, let hi = floor(b/k) and lo = floor(b/(k+1)). There are hi - lo numbers i such that k*i <= b < (k+1)*i, the sum of b % i for them is sum_{ lo < i <= hi } (b - k*i) = (hi - lo)*b - k*(hi-lo)*(hi+lo+1)/2.

如果 A＆LT; =开方（B），只有第一颗子弹适用，停在 A 。如果的sqrt（B）＆LT; A＆LT; b ，在第二点，从 K =楼（B / A）运行上限（开方（二） ）-1 键，调整为最小 K 上限 A 。

If a <= sqrt(b), only the first bullet applies, stopping at a. If sqrt(b) < a < b, in the second bullet, run from k = floor(b/a) to ceiling(sqrt(b))-1 and adjust the upper limit for the smallest k to a.

整体复杂度为O（分（A，开方（B）））。

Overall complexity O(min(a,sqrt(b))).

code（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;
}

这篇关于发现的范围内模运算的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！