숫자가 두 자리이면

Question

범위의 모 드 연산 합계를 찾은 다음 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 들어

Answer 1

우리 합계의 일부가 용이하게 (a >= b 경우, 0, 그렇지 (a-b)*b) 일정한 시간이 산출되도록, b % i == b있다.

i <= b의 부품은 계산되지 않습니다 (i == b은 0이므로 무시할 수 있음). 당신은 i <= sqrt(b)를 들어

• (SQRT (B)) 단계 O에서 그렇게 b % i을 계산하고 k = floor(b/i), 다음 b % i == b - k*i 및 k < sqrt(b)하자, i > 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 (분 (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; 
}