O（1）代碼來計算一個範圍內的數字的倍數？

Question

我該如何在恆定時間內做到這一點（我不想從a到b的迭代）？

// return number of multiples of c in [a,b] 
long count_multiples(int a, int b, int c) { 
    assert(b >= a && c != 0); 
    // todo 
    return -1; 
} 

這個問題看起來看似簡單，但難度比它看起來因爲它有一些極端情況如必須處理所有情況（a,b可以是負數/零並且c也可以是負數並且a可以等於b可以等於c）。在一種情況下，結果可能不適合32位（a = 2^31，b = 2^31-1,c = 1 or -1）

Answer 1

long count_multiples(int a, int b, int c) { 
    if (b < a) return 0; 
    if (c < 0) c = -c; 
    long al = a, bl = b, cl = c; 
    if (c == 1) return bl - al + 1; 
    return ((bl + (b < 0 ? 1 : 0))/cl) - 
      ((al - (a > 0 ? 1 : 0))/cl) + 
      ((a <= 0 && b >= 0) ? 1 : 0); 
}