c - 範囲内の数値の倍数をカウントする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すべてのケースを処理する必要があるなど、いくつかのコーナー ケースがあるため、見た目よりも難しいです( 結果は 1 つのケースで 32 ビットに収まらない場合があります ( 、、)bcabca = 2^31b = 2^31-1c = 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);
}