c++ - 如何找到给定范围内除以给定数字时具有一定余数的值的个数？

Question

给定四个整数N、L、R 和 Rem。我必须找到 L 和 R(包括)之间的值的数量，除以 N 时得到余数 Rem。

例如:如果N = 3、L = 2、R = 10 且 Rem = 1，则此范围内除以 3 余数为 1 的数字为 {4, 7 , 10}。所以，答案是3。

这是我编码的暴力方法:

int main() {
    int N, L, R, Rem;
    cin >> N >> L >> R >> Rem;

    int Ans = 0;
    for (int i = L; i <= R; i++) {
        if (i % N == Rem)
            Ans++;
    }
    cout << Ans << endl;
}

解决这个问题的更好方法是什么？

Answer 1

首先，查找 [0, n) 范围内此类值的数量:

template<class T>
T count(T n, T div, T rem) {
    assert(rem < div);
    return (n + div - rem - 1) / div;
}

然后减去 [0, max + 1) \ [0, min) = [min, max] :

template<class T>
T count(T min, T max, T div, T rem) {
    assert(min >= 0);
    assert(min <= max);
    return count(max + 1, div, rem) - count(min, div, rem);
}

<小时/>

Obviously, it doesn't work for negative values. The OP specified input as integers, not positive integers.

这个答案假设所有整数都是非负数。原因很简单:我们都同意非负数的余数是多少，但是 different definitions为负数而存在。问题措辞没有说明应该采用哪个定义。例如，在 C++11 之前的 C++ 本身中，标准指定了 a % b 的结果。如果 a < 0 则由实现定义或b < 0 。原因是在方式上存在以下差异/运算符是为整数操作数定义的:

• C++11 之前:

  The quotient is rounded in implementation-defined direction.

• 自 C++11 起:

  The quotient is truncated towards zero (fractional part is discarded).

因此，%和std::div可能会给出不同的结果 - 在 C++11 之前，后一个函数遵循“小数部分被丢弃”规则。