範囲

Question

にMOD操作の合計を見つけ、我々はsum of b%i where i ranges from 1 to aの値を見つけることができますどのように、その後a and b言うの？ 1つの方法は1からaまでのすべての値を反復することですが、効率的な方法はありますか？ （O（N）よりも良い？） 例えば：もし= 4、B = 5、必要なのANS = 5％1 + 5％2 + 5％3 + 5％4 = 4 おかげ。 i > bについて

Answer 1

和の一部が容易（(a-b)*b、a >= bもし、そうでなければ0）を一定時間で計算されるように、我々は、b % i == bを有します。 i <= bため

一部（従って無視することができる、i == bは0を返す）が計算されていません。あなたはO（SQRT（B））の手順、

i <= sqrt(b)については

• 、中b % iを計算し、b % i == b - k*i、その後、k = floor(b/i)せ、i > sqrt(b)については
• を合計し、k < sqrt(b)に追加することを行うことができます。したがって、k = 1〜ceiling(sqrt(b))-1の場合は、hi = floor(b/k)とlo = floor(b/(k+1))とします。 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あるiようhi - lo番号があります。

a <= sqrt(b)の場合は、最初の箇条書きのみが適用され、aで停止します。 sqrt(b) < a < b場合、第二弾では、k = floor(b/a)からceiling(sqrt(b))-1に実行し、aに最小kの上限を調整します。

全体の複雑さ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; 
}