發現在一系列

Question

模操作的總和，如果我們有2個號碼，說a and b那麼如何才能找到的sum of b%i where i ranges from 1 to a價值？ 一種方法是迭代所有值從1到一個，但有沒有任何有效的方法？ （比爲O（n）更好？） E.g：如果α= 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（開方（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（分鐘（一，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; 
}